构造用于 anbncm 的DPDA，其中n、m≥1（在TOC中）

DPDA是确定性下推自动机（DPDA）的简称。

问题

构造用于 anbncm 的DPDA，其中 m、n>=1

解决方案

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

L={abc,aabbc,aaabbbcc,…}

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

让我们计算a的数量，它等于b的数量。

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

然后对于c，什么也不会发生。

最后，在字符串的末尾，如果栈中没有任何东西剩下，那么我们可以说该语言在PDA中被接受。

给定问题的PDA如下：

转移函数

转移函数如下：

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

步骤2 - δ(q0, a, a) = (q0, aa)

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

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

步骤5 - δ(q1, c, Z) = (qf, Z)

步骤6 - δ(qf, c, Z) = (qf, Z)

解释

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

步骤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 - 第五个输入是'c'，栈顶为Z，规则为

     对于输入'c'，栈字母'Z'，状态为q1，则

     不做任何操作：(c,Z/Z)，状态将为qf

步骤8 - 第六个输入是'c'，栈顶为Z，规则为

     对于输入'c'，栈字母'Z'，状态为qf，则

     不做任何操作：(c,Z/Z)，状态将为qf

步骤9 - 我们到达了字符串的末尾，规则为

     如果我们处于最终状态qf，则字符串在PDA中被接受

更新于： 2021年6月15日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告