构造一个接受L = {anb(2n) | n>=1} ∪ {anbn | n>=1} 的下推自动机 (PDA)

下推自动机 (PDA) 可以形式化地描述为七元组

(Q, Σ,S, δ,q0,I,F)

其中：

• Q 是有限数量的状态
• Σ 是输入字母表
• S 是栈符号
• Δ 是转移函数: QX(Σ∪{e})XSXQ
• q0 是初始状态 (q0属于Q)
• I 是初始栈顶符号
• F 是一组接受状态

问题

构造 PDA 用于 L = {aⁿb⁽²ⁿ⁾ | n>=1} ∪ {aⁿbⁿ | n>=1}

解答

设

L = {aⁿb⁽²ⁿ⁾ | n>=1}

{aⁿbⁿ | n>=1}

构造 PDA 用于 L= L1 U L2

因此，由给定语言 L1 生成的字符串如下：

L1={abb,aabbbb,aaabbbbbb,….} 和

L2= {ab,aabb,aaabbb,….}

L= L1 U L2 = { abb,aabbbb,aaabbbbbb,….} U {ab,aabb,aaabbb,….}

对于语言 L1

在该语言中，a 后面跟着两倍数量的 b。

每当出现 ‘a’ 时，在栈中压入两个 ‘a’；如果再次出现 ‘a’，则重复此操作。

当出现 ‘b’ 时，每次从栈中弹出 一个 ‘a’。注意 b 出现在 ‘a’ 之后。

最终，如果字符串结束时栈为空，则可以声明 PDA 接受该语言。

对于语言 L2

对于语言 L2，我们必须计算相等数量的 a 和 b。

这可以通过在栈中压入 a，然后在出现 "b" 时弹出 a 来实现。

最终，如果字符串结束时栈为空，则可以声明 PDA 接受该语言。

该问题的 PDA 如下：

转移函数

转移函数如下：

步骤 1: δ(q0, a, Z) = (q1, aZ)

步骤 2: δ(q0, a, a) = (q3, aaz)

步骤 3: δ(q1, a, a) = (q1, aa)

步骤 4: δ(q1, b, a) = (q2, ε)

步骤 5: δ(q2, b, a) = (q2, ε)

步骤 6: δ(q2, ε, Z) = (qf1, Z)

步骤 7: δ(q3, a, a) = (q3, aaa)

步骤 8: δ(q3, b, a) = (q4, ε)

步骤 9: δ(q4, b, a) = (q4, ε)

步骤 10: δ(q4, ε, Z) = (qf2, Z)

Bhanu Priya

更新于：2021年6月15日

2K+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习