並非所有語法都是經過最佳化的，這意味著語法可能包含一些額外的符號（非終結符），從而增加語法的長度。因此，我們必須透過刪除無用符號來簡化語法。屬性下面解釋了簡化語法的屬性：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 如何比較輸入字串並做出接受或拒絕該字串的決策的非正式表示法。轉 stile 符號它用於連線表示 PDA 的一個或多個移動的 ID 對。轉換過程用轉 stile 符號“⊢”表示⊢ 表示一次移動。⊢ 符號描述一系列移動。示例(P, b, T) ⊢ (q, w, a)在從 P 到... 閱讀更多

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

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

問題定義語言 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 個磁帶磁頭獨立移動（多磁軌圖靈機的泛化）。δ=QxXN ->Q x XN x {L, R}NEach TM 有自己的讀寫磁頭，但狀態對所有磁頭都是通用的。多磁帶 TM 如下所示：在每個步驟（轉換）中，TM 讀取所有磁頭掃描的符號，根據這些符號和當前狀態，每個磁頭寫入、向右或向左移動，並且控制單元進入... 閱讀更多

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

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