並非所有語法都是經過最佳化的，這意味著語法可能包含一些額外的符號（非終結符），從而增加了語法的長度。因此，我們必須透過刪除無用符號來簡化語法。屬性下面解釋了簡化語法的屬性：G 中的每個非終結符和終結符都出現在某個單詞在 L 中的推導中。不應該有任何形式如 X->Y，其中 X 和 Y 是非終結符。如果 ε 不在語言 L 中，則在產生式 X-> ε 中不需要它。下圖描述了簡化語法的用法：型別為 S-> ε 的產生式是 ... 閱讀更多

上下文無關語言 (CFG) 的閉包性質如下：在並集運算下封閉為了證明上下文無關語言在並集運算下封閉，考慮兩個不同語言 L1 和 L2 的兩個起始變數 S1 和 S2。並集運算的語法如下所示：S -> S1 | S2如果這兩個語言都屬於上下文無關語言，則這兩個語言的並集也應該屬於上下文無關語言。根據以上定義，如果使用者生成 S1 和 S2 字串或兩者都生成，那麼在這種情況下，這兩個語言的並集就會生成。因此，L1 U L2 ∈ CFL所以，... 閱讀更多

在學習計算理論 (TOC) 中的遞迴可列舉語言之前，讓我們先了解遞迴語言的概念。遞迴語言如果某種語言 L 是某種圖靈機 (TM) 接受的字串集，並且該圖靈機在每個輸入上都停止，則該語言 L 是遞迴的（可判定的）。示例當圖靈機到達最終狀態時，它就會停止。我們也可以說，當圖靈機 M 達到狀態 q 並且要掃描的當前符號為“a”，使得 δ(q, a) 未定義時，圖靈機 M 就會停止。有些 TM 在某些輸入上永遠不會以任何一種方式停止，因此我們... 閱讀更多

下推自動機 (PDA) 的瞬時描述 (ID) 由三元組 (q, w, s) 表示其中，q 是狀態。w 是未消耗的輸入。s 是堆疊內容。ID 是 PDA 如何比較輸入字串並做出接受或拒絕該字串的決定的非正式表示法。轉向式符號它用於連線表示 PDA 一次或多次移動的 ID 對。轉換過程由轉向式符號“⊢”表示⊢ 表示一次移動。⊢ 符號描述了一系列移動。示例(P, b, T) ⊢ (q, w, a)在從 P 到... 閱讀更多

下推自動機 (PDA) 是一種以類似於為正則語法設計確定性有限自動機 (DFA) 的方式來實現上下文無關語法 (CFG) 的方法。DFA 可以記住有限量的資訊，但 PDA 可以記住無限量的資訊。基本上，PDA 如下所示：“有限狀態機 + 堆疊”PDA 有三個元件，如下所示：輸入帶。控制單元。一個大小無限的堆疊。PDA 可能會也可能不會讀取輸入符號，但它... 閱讀更多

上下文無關語法 (CFG) 肯定會被非確定性下推自動機 (NPDA) 識別，但程式語言透過確定性 PDA 轉換為二進位制（機器程式碼）。這是因為它具有以下提到的影響：如果程式語言應該透過 NPDA 翻譯，那麼對於一個給定的程式例項，我們將為同一個程式生成多個版本的二進位制（機器程式碼），這在理想情況下不應該發生。對於一個給定的程式，應該只生成一個版本的二進位制程式碼，並且該程式碼應該在所有作業系統平臺上保持一致。輸出將有很大差異：如果我們有多個目標檔案，那麼... 閱讀更多

問題定義語言 E={aibj|i 不等於 j 且 i 不等於 2j}，並設計一個生成 E 的喬姆斯基正規化 (CNF) 中的無歧義上下文無關語法 (CFG)。解決方案給定語言的無歧義 CFG 如下：S->AC|CBA->aA|aB->Bb|bC->aCb|aaCb|epsilon現在，將此 CFG 轉換為 CNF。您可以按照以下步驟進行成功的轉換。步驟 1首先新增一個新的起始符號 S0   S0->S   S->AC|CB   A->aA|a   B->Bb|b   C->aCb|aaCb|epsilon步驟 2接下來消除起始符號以外的產生式中的 epsilon 符號。   C->epsilon 是一個空產生式消除空產生式後，新的產生式如下：   S0->S   S->AC|CB   A->aA|a   B->Bb|b  ... 閱讀更多

具有多個磁帶的圖靈機 (TM) 稱為多磁帶圖靈機。每個磁帶都有自己的讀/寫磁頭對於 N 磁帶圖靈機 M={( Q, X, ∑, δ, q0, B, F)}我們將多磁帶圖靈機定義為具有 k 個磁帶和 k 個磁頭獨立移動的 k 磁帶（多磁軌圖靈機的推廣）。δ=QxXN -> Q x XN x {L, R}NEach TM 都有自己的讀寫磁頭，但狀態對所有磁頭都是通用的。多磁帶 TM 如下所示：在每個步驟（轉換）中，TM 讀取所有磁頭掃描的符號，根據這些符號和當前狀態，每個磁頭寫入、向右或向左移動，以及控制單元進入... 閱讀更多

雙棧下推自動機 (PDA) 包括以下因素：圖靈機可以接受任何具有一個棧的 PDA 都無法接受的語言。透過新增額外的棧來增強下推自動機的能力。具有兩個棧的 PDA 與圖靈機具有相同的計算能力。雙棧 PDA 是一種基於下推自動機 (PDA) 和非確定性雙棧 PDA 的推廣的計算模型，它等價於確定性雙棧 PDA。雙棧 PDA 的移動基於以下內容：有限控制的狀態。讀取的輸入符號。棧頂... 閱讀更多

類似於 PDA（部分 NFA）中的非確定性，對於一個輸入配置，可能有多個輸出。非確定性圖靈機類似於圖靈機，但具有有限數量的移動選擇；對於相同的輸入“當前狀態和當前符號”，可能有多個移動。如果至少存在一個計算對於輸入 w 正常停止，則非確定性圖靈機接受輸入 w。對於下推自動機，非確定性比確定性更強大。但對於有限自動機來說，這沒有區別。令人驚訝的是，確定性和非確定性圖靈機在能力上是相同的。注意：如果一個非確定性圖靈機接受語言 L，那麼... 閱讀更多