为 L = {0m1(n+m)2n | 构建下推自动机 m,n = 0} 在 C++ 中

我们得到了一种语言“L”，任务是为给定的语言构建一个下推自动机，它解释了 1 的出现将是 0 和 2 出现的相加，而且 0 和 2 的出现将是最少的一种也可以使字符串为 NULL 并且应该被自动机接受的方法。

什么是下推自动机？

下推自动机或下推自动机或 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 可接受的字符串形式为 -

• 0 ^m 1 ^m − 01, 0011, 000111 等。0s 的数量等于 no。1s。当 n 为 0 时，我们将没有 2。继续按 0，一旦遇到第一个 1，就弹出 0。如果我们到达字符串的末尾并且没有留下任何 0，则该字符串被接受。

• 1 ⁿ 2 ⁿ - 12、1122、111222 等。1s 的数量等于 no。2s。当 m 为 0 时，我们将没有 0。继续按 1，一旦遇到前 2，就弹出 1。如果我们到达字符串的末尾并且没有任何 1，那么该字符串被接受。

• 0 ⁿ 1 ^m+n 2 ^m − 0112, 001112, 001112 等。1s 的数量等于 no 的总和。0s 和 2s。一旦遇到第一个 1，就继续推 0，然后弹出 0，直到没有 0 剩下。现在再次按下 1 直到遇到第一个 2。然后每 2 开始弹出 1，直到我们没有 1。如果我们到达末尾并且没有剩下 1，那么字符串被接受。

• 也接受 NULL 字符串。0 ⁰ 1 ⁰ 2 ⁰

让我们了解机器

• 状态 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。