如果 L 是一个 CFL，那么 L* 是一个 CFL。这里 CFL 指的是上下文无关语言。步骤假设 L 的 CFG 具有非终结符 S、A、B、C、...。将非终结符从 S 更改为 S1。我们如下创建 L* 的新 CFG：包含 L 的 CFG 中的所有非终结符 S1、A、B、C、...。包含 L 的 CFG 的所有产生式。添加新的非终结符 S 和新的产生式S → S1S | ∧我们可以重复最后的产生式S → S1S → S1S1S → S1S1S1S → S1S1S1S1S → S1S1S1S1∧ → S1S1S1S1请注意，L* 中的任何单词都可以由... 阅读更多

这里 CFL 指的是上下文无关语言。现在，让我们了解一下连接运算下的闭包。连接运算下的闭包如果 L1 和 L2 是 CFL，那么 L1L2 是 CFL。按照以下步骤操作：L1 CFL 意味着 L1 有一个 CFG1 生成它。假设 CFG1 中的非终结符是 S、A、B、C、...。将 CFG1 中的非终结符更改为 S1、A1、B1、C1、...。不要更改 CFG1 中的终结符。L2 CFL 意味着 L2 有一个 CFG2 生成它。假设 CFG2 中的非终结符是 S、A、B、C、...。将 CFG2 中的非终结符更改为 S2、A2、... 阅读更多

如果 L1 和 L2 是 CFL，那么它们的并集 L1 + L2 是 CFL。这里 CFL 指的是上下文无关语言。L1 CFL 意味着 L1 有一个 CFG，假设它是 CFG1，生成它。假设 CFG1 中的非终结符是 S、A、B、C、...。将 CFG1 中的非终结符更改为 S1、A1、B1、C1、...。不要更改 CFG1 中的终结符。L2 CFL 意味着 L2 有一个 CFG，假设它是 CFG2，生成它。假设 CFG2 中的非终结符是 S、A、B、C、...。将 CFG2 中的非终结符更改为 S2、A2、... 阅读更多

让我们首先了解计算理论 (TOC) 中的子集。子集如果 A 和 B 是集合，则 A ⊂ B（A 是 B 的子集），如果 w ∈ A，则意味着 w ∈ B；也就是说，A 的每个元素也是 B 的元素。示例令 A = {ab, ba} 和 B = {ab, ba, aaa}。那么 A ⊂ B，但 B ⊄ A。令 A = {x, xx, xxx, ...} 和 B = {∧, x, xx, xxx, ...}。那么，A ⊂ B，但 B ⊄ A。令 A = {ba, ab} 和... 阅读更多

字母表上的字符串是字母表中字母的有限序列。示例toc、money、c 和 adedwxq 是字母表 ∑ = {a, b, c, ..., z} 上的字符串。84029 是字母表 ∑ = {0, 1, 2, ..., 9} 上的字符串。空字符串空字符串或空字符串，用 ∧ 表示，是不包含任何字母的字符串，无论我们正在考虑哪种类型的语言。字符串连接给定两个字符串 w1 和 w2，我们将 w1 和 w2 的连接定义为字符串 w1w2。示例如果 w1 = pq 和 w2 = ... 阅读更多

集合是对象的无序集合或元素的无序集合。集合总是用花括号 {} 括起来，集合中的元素写在花括号内。示例集合 {a, b, c} 有元素 a、b 和 c。集合 {a, b, c} 和 {b, c, b, a, a} 是相同的，因为顺序在集合中无关紧要，并且冗余也不算数。集合 {a} 有元素 a。请注意 {a} 和 a 是不同的东西；{a} 是一个只有一个元素 a 的集合。集合 {xn: n = 1, 2, 3, ... 阅读更多

上下文无关文法是四元组 G = (N, T, P, S)，其中，N 是非终结符的有限集，T 是终结符的有限集，N ∩ T = ∅，P 是形式为 A → α 的产生式的有限集，其中 A ∈ N，α ∈ (N ∪ T)*，S 是起始符号，S ∈ N。为语言 L = {anbm| m ≠n} 构造上下文无关文法情况 1n > m - 我们生成一个具有相同数量的 a 和 b 的字符串，并在左边添加额外的 a -S ... 阅读更多

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

确定性有限自动机 (DFA) 是五元组M=(Q, ∑, δ, q0, F)其中，Q - 有限集称为状态。∑ - 有限集称为字母表。δ - Q × ∑ → Q 是转移函数。q0 ∈ Q 是起始或初始状态。F - 结束或接受状态。让我们看看语言 A∩B 和 A* 的 DFA 中最坏情况下的状态数令 A 和 B 为两个状态，|A| = 状态数 = nA|B| = 状态数 = nBDFA = |A∩B|   =nA.nB|A ∪ B| =nA.nB|A*|=3/4 2nA|AB| = nA (2nB-2nB-1)NFA非确定性有限自动机 (NFA) 也有五个状态... 阅读更多

令 G = (V, T, P, S) 为 CFL。如果 P 中的每个产生式都具有如下所示的形式A -> aa其中 A 在 V 中，a 在 T 中，a 在 V* 中，则称 G 为 Greibach 范式 (GNF)。示例S -> aAB | bB A -> aA | aB -> bB | c定理 - 令 L 为不包含 {s} 的 CFL。则存在一个 GNF 文法 G 使得 L = L(G)。引理 1 - 令 L 为 CFL。则存在一个 PDA M 使得 L = LE(M)。证明... 阅读更多