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