下推自动机 (PDA) 可以形式化地描述为七元组 (Q, Σ, S, δ, q0, I, F)，其中：Q 是有限数量的状态；Σ 是输入字母表；S 是栈符号；Δ 是转移函数：Q × (Σ∪{e}) × S → Q × S；q0 是初始状态 (q0 ∈ Q)；I 是初始栈顶符号；F 是接受状态集 (F ∈ Q)。问题：为 0n1m2m3n (其中 n, m≥1) 构造 PDA。解答：该语言生成的字符串为：L={0123, 011223, 001233…}。1 和 3 的数量相同，2 和 1 的数量相同。给定问题的 PDA 构造… 阅读更多

下推自动机 (PDA) 可以形式化地描述为七元组 (Q, Σ, S, δ, q0, I, F)，其中：Q 是有限数量的状态；Σ 是输入字母表；S 是栈符号；Δ 是转移函数：Q × (Σ∪{e}) × S → Q × S；q0 是初始状态 (q0 ∈ Q)；I 是初始栈顶符号；F 是接受状态集。问题：为 a(n+m)bmcn (n, m≥1) 构造 PDA。解答：该语言生成的字符串为：L={aabc, aaaabccc, aaaaabbccc, …}。即 b 和 c 的数量之和等于 a 的数量。对于每个 b 和 c，我们将从… 阅读更多

图灵机 (TM) 可以形式化地描述为七元组：(Q, X, ∑, δ, q0, B, F)，其中：Q 是有限状态集；X 是带字母表；∑ 是输入字母表；δ 是转移函数：δ: Q × X → Q × X × {左移，右移}；q0 是初始状态；B 是空白符号；F 是最终状态集。当且仅当图灵机 T 从初始位置开始，x 写在磁带上，T 停留在最终状态时，图灵机 T 识别字符串 x（在 ∑ 上）。如果 x 被 T 识别，并且如果… 阅读更多

图灵机比有限自动机 (FA) 和下推自动机 (PDA) 都更强大。它们与我们制造的任何计算机一样强大。下面解释了图灵机相对于 PDA 的主要改进：无限“全部”可访问内存（以磁带的形式）——可以选择读取和写入。读/写头可以在输入磁带上向左和向右移动（或不改变位置）。TM 工作在一个无限的磁带上，磁带被分成单元格（在两个方向上都是无限的），每个单元格包含字母表中的一个符号或空白符号。… 阅读更多

与有限自动机 (FA) 类似，下推自动机 (PDA) 可以是确定性的或非确定性的。确定性下推自动机 (DPDA) 从不选择下一步：与确定性有限自动机 (DFA) 相比，它对每个状态、输入字符和栈字符的组合都有可能的输出。我们需要仔细考虑每个状态和栈字符的组合。只允许其中一个事务，要么针对空符号∧，要么针对输入符号。或者根本没有事务。示例：非确定性下推自动机 (NPDA) 可以包含以下指令，但是… 阅读更多

下推自动机用于实现上下文无关文法，就像我们使用一种技术为正则文法设计 DFA 一样。DFA 处理有限量的信息，而 PDA 处理无限量的信息。通常，下推自动机是： “有限状态机” + “一个栈”。下推自动机由三个部分组成：一个输入磁带、一个控制单元和一个无限大小的栈。现在考虑一个问题，如何为给定语言设计下推自动机：问题：设计一个识别偶数长度回文串的L = … 阅读更多

如果存在从起始状态到最终状态的某个路径（即指令序列）消耗字符串的所有字母，则非确定性下推自动机 (NPDA) 接受一个字符串。否则，字符串被 NPDA 拒绝。NPDA 的语言是它接受的所有字符串的集合。NPDA 在以下情况下拒绝输入字符串：如果读取输入字符串结束时未到达最终状态。如果对于当前状态/栈上的符号/输入符号不存在转移。如果它尝试弹出空栈。示例：构建一个识别… 阅读更多

非确定性下推自动机 (NPDA) 类似于有限自动机 (FA)，除了它们还有一个栈内存，可以在其中存储任意数量的信息。读/写栈内存作为 LIFO 工作：后进先出。我们可以用栈做什么？弹出操作读取顶部符号并将其从栈中删除，推送操作将指定的符号写入栈的顶部，例如 push(X) 表示将 X 放入栈顶，nop 操作对栈不执行任何操作。栈符号与输入磁带上使用的“语言”字母表不同。我们从… 阅读更多

上下文相关文法，其产生式形式为：αAβ → αγβ，其中 α, β ∈ (N ∪ T)*，A ∈ N；γ ∈ (N ∪ T)+，如果起始符号 S 不出现在任何规则的右侧，则允许规则 S → λ。这种文法生成的语言称为上下文相关语言。每个上下文无关文法也是上下文相关的 =⇒ 上下文无关语言是上下文相关语言的子集（参见乔姆斯基范式）。但是，并非每个上下文相关语言都是上下文无关的。示例：语言 {anbncn, n > 1} 是上下文相关的，但不是上下文无关的。一个… 阅读更多

正则文法是每个产生式采用以下受限形式之一的文法：B → ∧，B → w，B → A，B → wA。（其中 A、B 是非终结符，w 是非空终结符串。）正则文法的限制：在产生式的右侧最多只能出现一个非终结符。非终结符必须出现在右侧的右端。因此，产生式如下：A → aBc 和 S → TU 这些不是正则文法的一部分，但产生式 A → abcA 是。像 A → aB|cC 这样的内容是允许的，因为它们实际上是… 阅读更多