如果 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)。证明… 阅读更多