前置知识
下推自动机（PDA）类似于确定性有限自动机（DFA），但它比 DFA 具有更多的特性。用于实现 PDA 的数据结构是栈。PDA 会为每个输入产生一个关联的输出。所有输入要么被压入栈中，要么被直接忽略。我们可以对用于 PDA 的栈执行基本的入栈和出栈操作。DFA 面临的难题之一是无法计算输入给机器的字符数量。而 PDA 通过使用栈解决了这个问题，因为它为我们提供了这种计数能力。
下推自动机 (PDA) 可以定义为 –
M = (Q, Σ, Γ, δ, q0, Ζ, F) 其中
- Q 是状态的有限集合
- Σ 是一个有限集合，称为输入字母表
- Γ 是一个有限集合，称为栈字母表
- δ 是 Q X ( Σ ∪ {ε} X Γ X Q X Γ*) 的有限子集，即转移关系。
- q0 ∈ Q 是起始状态
- Ζ ∈ Γ 是初始栈符号
- F ⊆ Q 是接受状态的集合
状态转移的表示 –
PDA 中入栈的表示 –
PDA 中出栈的表示 –
PDA 中忽略的表示 –
问题 1) 为语言 L = {0n1m2m3n | n>=1, m>=1} 构建 PDA
该 PDA 采用的方法 –
首先将 0 压入栈中。然后将 1 压入栈中。
接着，对于每个作为输入的 2，从栈中弹出一个 1。如果还有一些 2 剩余，且栈顶是 0，那么该字符串不会被 PDA 接受。此后，如果 2 已经处理完毕且栈顶是 0，那么对于每个作为输入的 3，从栈中弹出一个 0。如果字符串结束且栈为空，则该字符串被 PDA 接受，否则不被接受。
- 步骤-1: 收到 0 时，将其压入栈中。收到 1 时，将其压入栈中并转移到下一个状态。
- 步骤-2: 收到 1 时，将其压入栈中。收到 2 时，从栈中弹出一个 1 并转移到下一个状态。
- 步骤-3: 收到 2 时，从栈中弹出一个 1。如果所有的 1 都已从栈中弹出，现在收到了 3，则从栈中弹出一个 0 并转移到下一个状态。
- 步骤-4: 收到 3 时，从栈中弹出一个 0。如果输入结束且栈为空，则转移到最终状态，字符串被接受。
示例：
输入 : 0 0 1 1 1 2 2 2 3 3
结果 : ACCEPTED (被接受)
输入 : 0 0 0 1 1 2 2 2 3 3
结果 : NOT ACCEPTED (未被接受)
问题 2) 为语言 L = {0n1m | n >= 1, m >= 1, m > n+2} 构建 PDA
该 PDA 采用的方法 –
首先将 0 压入栈中。当 0 处理完毕后，忽略两个 1。此后，对于每个作为输入的 1，从栈中弹出一个 0。当栈为空但仍有一些 1 剩余时，则忽略所有剩余的 1。
- 步骤-1: 收到 0 时，将其压入栈中。收到 1 时，忽略它并转移到下一个状态。
- 步骤-2: 收到 1 时，忽略它并转移到下一个状态。
- 步骤-3: 收到 1 时，从栈顶弹出一个 0 并转移到下一个状态。
- 步骤-4: 收到 1 时，从栈顶弹出一个 0。如果栈为空，收到 1 时忽略它并转移到下一个状态。
- 步骤-5: 收到 1 时忽略它。如果输入结束则转移到最终状态。
示例：
输入 : 0 0 0 1 1 1 1 1 1
结果 : ACCEPTED (被接受)
输入 : 0 0 0 0 1 1 1 1
结果 : NOT ACCEPTED (未被接受)