并非所有语法都是经过优化的，这意味着语法可能包含一些额外的符号（非终结符），从而增加语法的长度。因此，我们必须通过删除无用符号来简化语法。属性下面解释了简化语法的属性：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 如何比较输入字符串并做出接受或拒绝该字符串的决策的非正式表示法。转 stile 符号它用于连接表示 PDA 的一个或多个移动的 ID 对。转换过程用转 stile 符号“⊢”表示⊢ 表示一次移动。⊢ 符号描述一系列移动。示例(P, b, T) ⊢ (q, w, a)在从 P 到... 阅读更多

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

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

问题定义语言 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 个磁带磁头独立移动（多磁道图灵机的泛化）。δ=QxXN ->Q x XN x {L, R}NEach TM 有自己的读写磁头，但状态对所有磁头都是通用的。多磁带 TM 如下所示：在每个步骤（转换）中，TM 读取所有磁头扫描的符号，根据这些符号和当前状态，每个磁头写入、向右或向左移动，并且控制单元进入... 阅读更多

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

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