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