CFG 代表上下文无关文法，CNF 代表乔姆斯基范式，它们是计算理论中的概念。上下文无关文法 (CFG)上下文无关文法 (CFG) 是一种形式文法，用于生成给定形式语言中所有可能的字符串模式。它定义为四个元组 −G=(V, T, P, S)其中，G 是一个文法，它由一组产生式规则组成。它用于生成语言的字符串。T 是终结符的集合。它用小写字母表示。V 是非终结符的集合。它用大写字母表示…… 阅读更多

乔姆斯基范式简写为 CNF。如果产生式规则满足以下条件之一，则上下文无关文法处于 CNF 中：如果存在开始符号生成 ε。例如 − A-> ε如果非终结符生成两个非终结符。例如 − S->AB如果非终结符生成一个终结符。例如 − S->a示例让我们来看一下 G1 产生式规则，如下所示 −G1={ S->AB,          S->c,          A->a,          B->b}G1 满足 CNF 的规则。所以，它在 CNF 中。现在，让我们考虑 G2 产生式规则，如下所示 G2={ S->aA,          A->a,       ... 阅读更多

上下文无关文法 (CFG) 是一种形式文法，用于生成给定形式语言中所有可能的字符串模式。它定义为四个元组 −G=(V, T, P, S)其中，G 是一个文法，它由一组产生式规则组成。它用于生成语言的字符串。T 是终结符的集合。它用小写字母表示。V 是非终结符的集合。它用大写字母表示P 是一组产生式规则，用于替换非终结符 (左侧)…… 阅读更多

判定问题 Q 是一组问题，每个问题都有“是”或“否”的答案。让我们考虑一下这个问题：“10 是否是完全平方数？”，这是一个判定问题的例子。判定问题通常包含无限数量的相关问题。示例问题 PSQ 确定任意自然数是否是完全平方数，其中包含一些有疑问的问题，例如以下问题 −q0：0 是否是完全平方数？q1：1 是否是完全平方数？q2：2 是否是完全平方数？解决方案判定问题 Q 的解决方案是一种算法，它确定对……的近似答案 阅读更多

瞬时描述被称为非正式符号，它解释了下推自动机 (PDA) 如何计算给定的输入字符串并做出关于接受或拒绝该字符串的决策。PDA 包括状态和堆栈的内容。堆栈通常是 PDA 在任何时候的重要部分之一。因此，我们为描述字符串处理的 PDA 的连续配置制作了一个方便的符号。PDA 符号的三元组 (q, w, γ) 的因素是 q 是当前状态。w 是剩余的输入字母。γ 是 PDA 堆栈的当前内容。通常，最左边的符号…… 阅读更多

DFA 是确定性有限自动机的缩写，NFA 是非确定性有限自动机的缩写。现在，让我们详细了解这两种有限自动机。DFA确定性有限自动机是五元组自动机。以下是 DFA 的定义 −M=(Q, Σ, δ, q0, F)其中，Q：称为状态的有限集。Σ：称为字母表的有限集。δ：Q × Σ → Q 是转换函数。q0 ϵ Q 是起始状态或初始状态。F：最终状态或接受状态。NFA NFA 也与 DFA 具有相同的五个状态，但转换函数不同，如下所示 −δ: Q X Σ ... 阅读更多

自动机不过是一种接受输入字母表 Σ 上语言 L 的字符串的机器。计算理论 (TOC) 中主要使用了四种不同类型的自动机。这些如下所示 − 有限状态机 (FSM)。下推自动机 (PDA)。线性有界自动机 (LBA)。图灵机 (TM)。比较这四种类型的自动机时，有限状态机功能较弱，而图灵机功能更强大。注意 − 确定性有限自动机 (DFA) 和非确定性有限自动机 (NFA) 具有相同的强大功能，因为每个 DFA…… 阅读更多

如果文法不包含歧义，则该文法可以是无歧义的。这意味着如果它不包含多个最左推导 (LMD) 或多个最右推导 (RMD) 或给定输入字符串的多个语法树，则它就是一个无歧义的文法。规则为了将歧义文法转换为无歧义文法，我们应用以下规则 −规则 1 − 如果在产生式规则中使用左结合运算符 (+, -, *, /)，则在产生式规则中应用左递归。左递归不过是右侧最左边的符号…… 阅读更多

对于以下每种语言，绘制接受它的有限自动机 (FA)。{a, b}*{a}该语言指出自动机接受包含任意数量的 a 和 b 且最终以 a 结尾的字符串。该语言的有限状态自动机如下所示 −{a, b}*{b, aa}{a, b*}该语言指出自动机接受以任意数量的 a 和 b 开头和结尾并包含子串 b 和 aa 的字符串。该语言的有限状态自动机如下所示 −{bbb, baa}*{a}该语言指出自动机接受包含任意数量的 bbb 和 baa…… 阅读更多

如果存在给定输入字符串的多个最左推导或多个最右推导或多个语法树，则称文法是歧义的。如果文法不是歧义的，则我们称之为无歧义文法。如果文法存在歧义，则它对于编译器构造是有好处的。没有方法可以自动检测和消除歧义，但我们可以通过重写整个文法而不含歧义来消除歧义。示例让我们考虑一个具有如下所示的产生式规则的文法 −E = IE = E+EE = E*EE = (E)E = ε|0|1|2|3...9让我们考虑一个…… 阅读更多