数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用C++构建用于语言L = {0m1(n+m)2n | m,n = 0} 的下推自动机
我们给定了一种语言“L”，任务是为给定的语言构建一个下推自动机，它解释了1的出现次数将是0和2的出现次数之和，并且0和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可接受的字符串形式为：
0m1m - 01, 0011, 000111等。0的个数等于1的个数。当n为0时，我们将没有2。持续压入0，一旦遇到第一个1，则弹出0。如果我们到达字符串的末尾并且没有剩余的0，则接受该字符串。
1n2n - 12, 1122, 111222等。1的个数等于2的个数。当m为0时，我们将没有0。持续压入1，一旦遇到第一个2，则弹出1。如果我们到达字符串的末尾并且没有剩余的1，则接受该字符串。
0n1m+n2m - 0112, 001112, 001112等。1的个数等于0和2的个数之和。持续压入0，一旦遇到第一个1，则弹出0，直到没有剩余的0。现在再次压入1，直到遇到第一个2。然后，对于每个2，开始弹出1，直到我们没有剩余的1。如果我们到达末尾并且没有剩余的1，则接受该字符串。
空字符串也被接受。001020
让我们了解一下机器
状态q0的转移：
( 0, I/0I ) - 如果堆栈顶部为I且当前输入符号为0，则将0压入堆栈顶部并保持在q0。堆栈变为0I...
( 0, 0/00 ) - 如果堆栈顶部为0且当前输入符号也为0，则将0压入堆栈顶部并保持在q0。堆栈变为00.... 持续压入0，直到下一个1或2。
( 1, I/1I ) - 如果堆栈顶部为I且当前输入符号为1，则将1压入堆栈顶部并移动到q1。堆栈变为1I...
( 1, 0/$ ) - 如果堆栈顶部为0且当前输入符号为1，则弹出0并移动到q1。
( 1, 0/$ ) - 如果堆栈顶部为0且当前输入符号为1，则弹出0并移动到q1。
状态q1的转移：
( 1, 1/11 ) - 如果堆栈顶部为1且当前输入符号也为1，则将1压入堆栈顶部并保持在q1。堆栈变为11.... 持续压入1，直到下一个0或2。
( 1, 0/$ ) - 如果堆栈顶部为0且当前输入符号为1，则弹出0并保持在q1。
( $, I/I ) - 如果堆栈顶部为I且没有输入，则不执行任何操作并移动到qf。
( 2, 1/$ ) - 如果堆栈顶部为1且当前输入符号为2，则弹出1并移动到q2。
状态q2的转移：
( 2, 1/$ ) - 如果堆栈顶部为1且当前输入符号为2，则弹出1并保持在q2。
( $, I/I ) - 如果堆栈顶部为I且没有输入，则不执行任何操作并移动到qf。
482 次浏览
