如果 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)。證明... 閱讀更多