下推自动机 (PDA) 可以正式描述为七元组 (Q, Σ, S, δ, q0, I, F)其中，Q 是有限数量的状态Σ 是输入字母表S 是栈符号Δ 是转移函数：QX(Σ∪{e})XSXQq0 是初始状态 (q0 属于 Q)I 是初始状态栈顶符号F 是一个接受状态集 (F 属于 Q)问题为 0n1m2m3n 其中 n, m≥1 构造 PDA。解决方案因此，由给定语言生成的字符串为 -L={0123, 011223, 001233….}1 和 3 的数量相同，2 和 1 的数量相同给定问题的 PDA 构造PDA 为… 阅读更多

下推自动机 (PDA) 可以正式描述为七元组 (Q, Σ, S, δ, q0, I, F)其中，Q 是有限数量的状态Σ 是输入字母表S 是栈符号Δ 是转移函数：QX(Σ∪{e})XSXQq0 是初始状态 (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 是带字母表。∑ 是输入字母表。δ 是转移函数：𝛿:QxX->QxXx{左移，右移}。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 这样的内容是允许的，因为它们实际上… 阅读更多