构造用于anbn（其中n>=1）的确定性下推自动机 (DPDA)

问题

构造一个确定性下推自动机 (DPDA) 用于anbn，其中 n>=1。

解答

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

L={ab, aabb, aaabbb,…}

也就是说，我们必须计算相同数量的a和b。

这可以通过将a压入堆栈，然后在出现“b”时弹出a来实现。

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

状态转换图如下：

转移函数

转移函数如下：

δ(q0, a, Z) = (q0, aZ)

δ(q0, a, a) = (q0, aa)

δ(q0, b, a) = (q1, ε)

δ(q1, b, a) = (q1, ε)

δ(q1, ε, Z) = (qf, Z)

解释

步骤1 - 让我们取一个输入字符串：“aabb”。

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

步骤3 - 第一个输入是'a'，规则是：

     输入'a'，堆栈字母为Z，则

     将输入'a'压入堆栈：(a,Z/aZ)，状态将为q0。

步骤4 - 第二个输入是'a'，规则是：

     输入'a'，堆栈字母为'a'，则

     将输入'a'压入堆栈：(a,a/aa)，状态将为q0。

步骤5 - 第三个输入是'b'，规则是：

     输入'b'，堆栈字母为'a'，则

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

步骤6 - 第四个输入是'b'，规则是：

     输入'b'，堆栈字母为'a'，状态为q1，则

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

步骤7 - 我们到达了字符串的末尾，规则是：

     输入ε，堆栈字母为Z，进入最终状态(qf)：(ε, Z/Z)

更新于：2021年6月15日

29K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告