并非所有语法都是经过优化的，这意味着语法可能包含一些额外的符号（非终结符），从而增加了语法的长度。因此，我们必须通过删除无用符号来简化语法。属性下面解释了简化语法的属性：G 中的每个非终结符和终结符都出现在某个单词在 L 中的推导中。不应该有任何形式如 X->Y，其中 X 和 Y 是非终结符。如果 ε 不在语言 L 中，则在产生式 X-> ε 中不需要它。下图描述了简化语法的用法：类型为 S-> ε 的产生式是 ... 阅读更多

上下文无关语言 (CFG) 的闭包性质如下：在并集运算下封闭为了证明上下文无关语言在并集运算下封闭，考虑两个不同语言 L1 和 L2 的两个起始变量 S1 和 S2。并集运算的语法如下所示：S -> S1 | S2如果这两个语言都属于上下文无关语言，则这两个语言的并集也应该属于上下文无关语言。根据以上定义，如果用户生成 S1 和 S2 字符串或两者都生成，那么在这种情况下，这两个语言的并集就会生成。因此，L1 U L2 ∈ CFL所以，... 阅读更多

在学习计算理论 (TOC) 中的递归可枚举语言之前，让我们先了解递归语言的概念。递归语言如果某种语言 L 是某种图灵机 (TM) 接受的字符串集，并且该图灵机在每个输入上都停止，则该语言 L 是递归的（可判定的）。示例当图灵机到达最终状态时，它就会停止。我们也可以说，当图灵机 M 达到状态 q 并且要扫描的当前符号为“a”，使得 δ(q, a) 未定义时，图灵机 M 就会停止。有些 TM 在某些输入上永远不会以任何一种方式停止，因此我们... 阅读更多

下推自动机 (PDA) 的瞬时描述 (ID) 由三元组 (q, w, s) 表示其中，q 是状态。w 是未消耗的输入。s 是堆栈内容。ID 是 PDA 如何比较输入字符串并做出接受或拒绝该字符串的决定的非正式表示法。转向式符号它用于连接表示 PDA 一次或多次移动的 ID 对。转换过程由转向式符号“⊢”表示⊢ 表示一次移动。⊢ 符号描述了一系列移动。示例(P, b, T) ⊢ (q, w, a)在从 P 到... 阅读更多

下推自动机 (PDA) 是一种以类似于为正则语法设计确定性有限自动机 (DFA) 的方式来实现上下文无关语法 (CFG) 的方法。DFA 可以记住有限量的信息，但 PDA 可以记住无限量的信息。基本上，PDA 如下所示：“有限状态机 + 堆栈”PDA 有三个组件，如下所示：输入带。控制单元。一个大小无限的堆栈。PDA 可能会也可能不会读取输入符号，但它... 阅读更多

上下文无关语法 (CFG) 肯定会被非确定性下推自动机 (NPDA) 识别，但编程语言通过确定性 PDA 转换为二进制（机器代码）。这是因为它具有以下提到的影响：如果编程语言应该通过 NPDA 翻译，那么对于一个给定的程序实例，我们将为同一个程序生成多个版本的二进制（机器代码），这在理想情况下不应该发生。对于一个给定的程序，应该只生成一个版本的二进制代码，并且该代码应该在所有操作系统平台上保持一致。输出将有很大差异：如果我们有多个目标文件，那么... 阅读更多

问题定义语言 E={aibj|i 不等于 j 且 i 不等于 2j}，并设计一个生成 E 的乔姆斯基范式 (CNF) 中的无歧义上下文无关语法 (CFG)。解决方案给定语言的无歧义 CFG 如下：S->AC|CBA->aA|aB->Bb|bC->aCb|aaCb|epsilon现在，将此 CFG 转换为 CNF。您可以按照以下步骤进行成功的转换。步骤 1首先添加一个新的起始符号 S0   S0->S   S->AC|CB   A->aA|a   B->Bb|b   C->aCb|aaCb|epsilon步骤 2接下来消除起始符号以外的产生式中的 epsilon 符号。   C->epsilon 是一个空产生式消除空产生式后，新的产生式如下：   S0->S   S->AC|CB   A->aA|a   B->Bb|b  ... 阅读更多

具有多个磁带的图灵机 (TM) 称为多磁带图灵机。每个磁带都有自己的读/写磁头对于 N 磁带图灵机 M={( Q, X, ∑, δ, q0, B, F)}我们将多磁带图灵机定义为具有 k 个磁带和 k 个磁头独立移动的 k 磁带（多磁道图灵机的推广）。δ=QxXN -> Q x XN x {L, R}NEach TM 都有自己的读写磁头，但状态对所有磁头都是通用的。多磁带 TM 如下所示：在每个步骤（转换）中，TM 读取所有磁头扫描的符号，根据这些符号和当前状态，每个磁头写入、向右或向左移动，以及控制单元进入... 阅读更多

双栈下推自动机 (PDA) 包括以下因素：图灵机可以接受任何具有一个栈的 PDA 都无法接受的语言。通过添加额外的栈来增强下推自动机的能力。具有两个栈的 PDA 与图灵机具有相同的计算能力。双栈 PDA 是一种基于下推自动机 (PDA) 和非确定性双栈 PDA 的推广的计算模型，它等价于确定性双栈 PDA。双栈 PDA 的移动基于以下内容：有限控制的状态。读取的输入符号。栈顶... 阅读更多

类似于 PDA（部分 NFA）中的非确定性，对于一个输入配置，可能有多个输出。非确定性图灵机类似于图灵机，但具有有限数量的移动选择；对于相同的输入“当前状态和当前符号”，可能有多个移动。如果至少存在一个计算对于输入 w 正常停止，则非确定性图灵机接受输入 w。对于下推自动机，非确定性比确定性更强大。但对于有限自动机来说，这没有区别。令人惊讶的是，确定性和非确定性图灵机在能力上是相同的。注意：如果一个非确定性图灵机接受语言 L，那么... 阅读更多