数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用C++构造用于L = {0n1m2m3n | m,n ≥ 0}的下推自动机
我们得到了一种语言“L”，任务是为这种语言构造一个下推自动机。该语言规定0的出现次数与3的出现次数相等，1的出现次数与2的出现次数相等，并且所有数字的出现次数都至少为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 接受的字符串形式为：
0n3n - 03, 0033, 000333 等。0 的数量等于 3 的数量。当 m 为 0 时，将没有 1 和 2。不断压入 0，一旦遇到第一个 3，就弹出 0。如果到达字符串末尾并且没有剩余的 0，则接受该字符串。
1m2m - 12, 1122, 111222 等。1 的数量等于 2 的数量。当 n 为 0 时，将没有 0 和 3。不断压入 1，一旦遇到第一个 2，就弹出 1。如果到达字符串末尾并且没有剩余的 1，则接受该字符串。
0n1m2m3n - 0123, 001233, 011223 等。0 的数量等于 3 的数量，1 的数量等于 2 的数量。不断压入 0 和 1。一旦遇到第一个 2，如果栈顶是 1 就弹出 1，然后对于其余的 3 弹出 0。如果到达字符串末尾并且没有剩余的 0，则接受该字符串。
空字符串也被接受：00102030。
让我们理解这个机器
状态 q0 的转移：
( 0, I/0I ) − 如果栈顶是 I 且当前输入符号是 0，则将 0 压入栈顶并停留在 q0。栈变为 0I…
( 0, 0/00 ) − 如果栈顶是 0 且当前输入符号也是 0，则将 0 压入栈顶并停留在 q0。栈变为 00… 不断压入 0 直到下一个 1 或 3。
( 1, 0/10 ) − 如果栈顶是 0 且当前输入符号是 1，则将 1 压入栈顶并移动到 q1。栈变为 10…
( 1, I/1I ) − 如果栈顶是 I 且当前输入符号是 1，则压入 1 并移动到 q5。
( 3, 0/ε ) − 如果栈顶是 0 且当前输入符号是 3，则弹出 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。
( 3, 0/ε ) − 如果栈顶是 0 且当前输入符号是 3，则弹出 0 并移动到 q3。
状态 q3 的转移：
( 3, 0/ε ) − 如果栈顶是 0 且当前输入符号是 3，则弹出 0 并停留在 q3。
( $, 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。（空字符串的情况）
605 次浏览
