数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究构建用于 a(n+m)bmcn (n,m≥1) 的 DPDA（在 TOC 中）
下推自动机 (PDA) 可以正式地描述为七元组
(Q, Σ,S, δ,q0,I,F)
其中，
- Q 是有限数量的状态
- Σ 是输入字母表
- S 是栈符号
- Δ 是转移函数：QX(Σ∪{e})XSXQ
- q0 是初始状态（q0 属于 Q）
- I 是初始栈顶符号
- F 是接受状态集
问题
构建用于 a(n+m)bmcn (n,m≥1) 的 PDA。
解决方案
因此，由给定语言生成的字符串为 -
L={aabc,aaaabccc,aaaaabbccc,….}
也就是说，将 b 和 c 的数量相加，这将等于 a 的数量。
对于每个 b 和 c，我们将从栈中弹出 a。
让我们计算 a 的数量，它等于 b 和 c 的数量之和。
可以通过将 a 推入栈中来实现，然后在出现“b”或“c”时弹出 a。
最后，在字符串的末尾，如果栈中没有剩余任何内容，那么我们可以说 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, a) = (q2, ε)
步骤 6：δ(q2, c, a) = (q2, ε)
步骤 7：δ(q2, ε, Z) = (qf, Z)
解释
步骤 1 - 让我们取一个输入字符串：“aaaabbcc”，它满足给定条件。
步骤 2 - 从左到右扫描字符串。
步骤 3 - 对于输入 'a' 和栈字母 Z，则
将输入 'a' 推入栈中：(a,Z/aZ)，状态将为 q0
步骤 4 - 对于输入 'a' 和栈字母 'a'，则
将输入 'a' 推入栈中：(a,a/aa)，状态将为 q0
步骤 5 - 对于输入 'a' 和栈字母 'a'，则
将输入 'a' 推入栈中：(a,a/aa)，状态将为 q0
步骤 6 - 对于输入 'a' 和栈字母 'a'，则
将输入 'a' 推入栈中：(a,a/aa)，状态将为 q0
步骤 7 - 对于输入 'b' 和栈字母 'a'，状态为 q0，则
弹出 'a'：(c,a/ε)，状态将为 q1
步骤 8 - 对于输入 'b' 和栈字母 'a'，状态为 q1，则
弹出 'a'：(c,a/ε)，状态保持为 q1
步骤 9 - 对于输入 'c' 和栈字母 'a'，状态为 q1，则
弹出 'a'：(c,a/ε)，状态将为 q2
步骤 10 - 对于输入 'c' 和栈字母 'a'，状态为 q2，则
弹出 'a'：(c,a/ε)，状态保持为 q2
步骤 11 - 我们到达了字符串的末尾，输入为 ε，栈字母为 Z，则
转到最终状态(qf)：(ε, Z/Z)
879 次浏览
