构造一个用于anb2n (n ≥ 1) 的确定性下推自动机 (DPDA)

确定性有限自动机 (DFA) 只能记住有限的信息，而下推自动机 (PDA) 则可以记住无限的信息。

基本上，PDA 如下所示：

“有限状态机 + 堆栈”

PDA 有三个组成部分：

• 输入带
• 控制单元
• 大小无限的堆栈

PDA 可以正式描述为七元组 (Q, Σ, S, δ, q0, I, F)

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

问题

构造一个用于 aⁿb²ⁿ (n ≥ 1) 的 PDA。

解决方案

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

L={abb,aabbbb,aaabbbbbb,…}

这里 a 后面跟着两倍数量的 b。

每当出现 'a' 时，就在堆栈中压入两个 'a'，如果再次出现 'a'，则执行相同的操作。

当出现 'b' 时，每次从堆栈中弹出 'a'。请注意，'b' 出现在 'a' 之后。

最后，在字符串结束时，如果堆栈中没有任何内容，那么我们可以声明该语言在 PDA 中被接受。

问题的PDA 如下所示：

转移函数

转移函数如下所示：

步骤 1：δ(q0, a, Z) = (q0, aaZ)

步骤 2：δ(q0, a, a) = (q0, aaa)

步骤 3：δ(q0, b, a) = (q1, ε)

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

步骤 5：δ(q1, ε, Z) = (qf, Z)

解释

步骤 1 - 考虑输入字符串：“aabbbb”，它满足给定条件。

步骤 2 - 从左到右扫描字符串。

步骤 3 - 对于输入 'a' 和堆栈字母 Z，则

步骤 4 - 对于输入 'a' 和堆栈字母 'a'，则

将两个 'a' 压入堆栈：(a,a/aaa)，状态将为 q0。现在堆栈有“aaaa”。

步骤 5 - 对于输入 'b' 和堆栈字母 'a'，则

从堆栈中弹出 'a'：(b,a/ε)，状态将为 q1。

步骤 6 - 对于输入 'b'，堆栈字母 'a' 和状态 q1，则

从堆栈中弹出 'a'：(b,a/ε)，状态将保持 q1

步骤 7 - 对于输入 'b' 和堆栈字母 'a'，则

从堆栈中弹出 'a'：(b,a/ε)，状态将为 q1

步骤 8 - 对于输入 'b'，堆栈字母 'a' 和状态 q1，则

从堆栈中弹出 'a'：(b,a/ε)，状态将保持 q1

步骤 9 - 我们到达字符串末尾，对于输入 ε 和堆栈字母 Z，

转到最终状态 (qf)：(ε, Z/Z)

Bhanu Priya

更新于：2021年6月15日

2万+ 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习