数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究用C++构建用于L = {0n1m2(n+m) | m,n ≥ 0}的向下推自动机
我们得到了一种语言“L”，任务是为该语言构建一个下推自动机，这说明2的出现次数将是0和1出现次数的和，并且0和1的出现次数至少为一，也可以使字符串为空，并且应该被自动机接受。
什么是下推自动机？
下推自动机（PDA）是一种以类似于我们为正则文法设计确定性有限自动机 (DFA) 的方式实现上下文无关文法的方法。DFA可以操作有限数据，但PDA可以操作无限数据。我们可以将下推自动机理解为“有限状态机”和“堆栈”的组合。
下推自动机具有三个组成部分：
一个输入带；
一个控制单元；以及
一个无限大小的堆栈。
PDA可以形式化地描述为一个7元组 (Q, Σ, S, δ, q0, I, F)：
Q是有限数量的状态
Σ是输入字母表
S是堆栈符号
δ是转移函数：Q × (Σ υ {ε}) × S × Q × S*
q0是初始状态 (q0 ∈ Q)
I是初始堆栈顶部符号 (I ∈ S)
F是一组接受状态 (F ∈ Q)
**让我们为给定的语言构建一个下推自动机：**
这个PDA可以接受的字符串形式为：
0n2n - 02, 0022, 000222 等。0的个数等于2的个数。当m为0时，我们将没有1。不断压入0，一旦遇到第一个2，则弹出0。如果我们到达字符串的末尾并且没有剩余的0，则接受该字符串。
1m2m - 12, 1122, 111222 等。1的个数等于2的个数。当n为0时，我们将没有0。不断压入1，一旦遇到第一个2，则弹出1。如果我们到达字符串的末尾并且没有剩余的1，则接受该字符串。
0n1m2m+n - 0122, 001112, 001112 等。2的个数等于0和1个数之和。不断压入0和1。一旦遇到第一个2，则弹出1和0。如果我们到达字符串的末尾并且没有剩余的0，则接受该字符串。
空字符串也被接受。001020。
让我们了解一下这个机器
状态q0的转移
-(0, I/0I) - 如果堆栈顶部是I且当前输入符号是0，则将0压入堆栈顶部并保持在q0。堆栈变为0I…
(0, 0/00) - 如果堆栈顶部是0且当前输入符号也是0，则将0压入堆栈顶部并保持在q0。堆栈变为00… 继续压入0，直到下一个1或2。
(1, 0/10) - 如果堆栈顶部是0且当前输入符号是1，则将1压入堆栈顶部并移动到q1。堆栈变为10…
(1, I/I) - 如果堆栈顶部是I且当前输入符号是1，则什么也不做并移动到q5。
(2, 0/ε) - 如果堆栈顶部是0且当前输入符号是2，则弹出0并移动到q3。
($, I/I) - 如果堆栈顶部是I且没有输入，则什么也不做并移动到q4。对于空字符串。
状态q1的转移
-(1, 1/11) - 如果堆栈顶部是1且当前输入符号也是1，则将1压入堆栈顶部并保持在q1。堆栈变为11… 继续压入1，直到下一个2。
(2, 1/ε) - 如果堆栈顶部是1且当前输入符号是2，则弹出1并移动到q2。
状态q2的转移
-(2, 1/ε) - 如果堆栈顶部是1且当前输入符号是2，则弹出1并保持在q2。
(2, 0/ε) - 如果堆栈顶部是0且当前输入符号是2，则弹出0并移动到q3。
状态q3的转移
-(2, 0/ε) - 如果堆栈顶部是0且当前输入符号是2，则弹出0并移动到q4。
($, I/I) - 如果堆栈顶部是I且没有输入，则什么也不做并移动到q4。对于空字符串。
状态q5的转移
-(1, 1/11) - 如果堆栈顶部是1且当前输入符号也是1，则将1压入堆栈顶部并保持在q5。堆栈变为11… 继续压入1，直到下一个2。
(2, 1/ε) - 如果堆栈顶部是1且当前输入符号是2，则弹出1并移动到q6。
状态q6的转移
-(2, 1/ε) - 如果堆栈顶部是1且当前输入符号是2，则弹出1并保持在q6。
($, I/I) - 如果堆栈顶部是I且没有输入，则什么也不做并移动到q4。对于空字符串。
浏览量：302
