下推自動機 (PDA) 可以正式描述為七元組 (Q, Σ, S, δ, q0, I, F)其中，Q 是有限數量的狀態Σ 是輸入字母表S 是棧符號Δ 是轉移函式：QX(Σ∪{e})XSXQq0 是初始狀態 (q0 屬於 Q)I 是初始狀態棧頂符號F 是一個接受狀態集 (F 屬於 Q)問題為 0n1m2m3n 其中 n, m≥1 構造 PDA。解決方案因此，由給定語言生成的字串為 -L={0123, 011223, 001233….}1 和 3 的數量相同，2 和 1 的數量相同給定問題的 PDA 構造PDA 為… 閱讀更多

下推自動機 (PDA) 可以正式描述為七元組 (Q, Σ, S, δ, q0, I, F)其中，Q 是有限數量的狀態Σ 是輸入字母表S 是棧符號Δ 是轉移函式：QX(Σ∪{e})XSXQq0 是初始狀態 (q0 屬於 Q)I 是初始狀態棧頂符號F 是一個接受狀態集問題為 a(n+m)bmcn n, m≥1 構造 PDA。解決方案因此，由給定語言生成的字串為 -L={aabc, aaaabccc, aaaaabbccc, ….}也就是說，將 b 和 c 的數量相加，這將等於 a 的數量。對於每個 b 和 c，我們將從… 閱讀更多

圖靈機 (TM) 可以正式描述為七元組 -(Q, X, ∑, δ, q0, B, F)其中，Q 是一個有限狀態集。X 是帶字母表。∑ 是輸入字母表。δ 是轉移函式：𝛿:QxX->QxXx{左移，右移}。q0 是初始狀態。B 是空白符號。F 是最終狀態。當且僅當 T 從初始位置開始，x 寫在磁帶上，T 停止在最終狀態時，圖靈機 T 識別字符串 x（在 ∑ 上）。如果 x 被 T 識別，並且如果… 閱讀更多

圖靈機比有限自動機 (FA) 和下推自動機 (PDA) 都更強大。它們與我們構建的任何計算機一樣強大。圖靈機中與 PDA 相比的主要改進如下所述 -無限“全部”可訪問記憶體（以磁帶的形式）– 選項讀取和寫入它。讀/寫頭可以在輸入磁帶上向左和向右移動（或不改變位置）。TM 在一個無限的磁帶上工作，該磁帶被分成單元格（雙向無限），每個單元格包含字母表中的符號或空白符號。… 閱讀更多

與有限自動機 (FA) 類似，下推自動機 (PDA) 可以是確定性的或非確定性的。確定性下推自動機 (DPDA) 從不選擇下一步 -與確定性有限自動機 (DFA) 相比，它對每個狀態、輸入字元和棧字元組合都有可能的輸出。我們需要小心處理每個狀態和棧字元的組合。只允許一個事務，無論是空符號 ∧ 還是輸入符號。或者根本沒有事務。示例非確定性下推自動機 (NPDA) 可以包含以下指令，但… 閱讀更多

下推自動機用於實現上下文無關語法，就像我們使用一種技術為正則語法設計 DFA 一樣。DFA 在有限量的資訊上工作，而 PDA 在無限量的資訊上工作。通常，下推自動機是 -"有限狀態機" + "一個棧"下推自動機由三個元件組成 -一個輸入磁帶，一個控制單元，以及一個無限大小的棧。現在考慮一個問題，即如何為給定語言設計下推自動機 -問題設計一個識別偶數長度迴文串的下推自動機，用於 L =… 閱讀更多

如果存在從起始狀態到最終狀態的某個路徑（即指令序列）消耗字串的所有字母，則非確定性下推自動機 (NPDA) 接受字串。否則，字串會被 NPDA 拒絕。NPDA 的語言是它接受的所有字串的集合。在以下情況下，NPDA 拒絕輸入字串 -如果在沒有到達最終狀態的情況下完成讀取輸入字串。如果對於當前狀態/棧上的符號/輸入符號不存在轉換。如果它試圖彈出空棧。示例構建一個識別… 閱讀更多

非確定性下推自動機 (NPDA) 類似於有限自動機 (FA)，除了它們還有一個棧記憶體，可以在其中儲存任意數量的資訊。讀/寫棧記憶體的工作方式為 LIFO：後進先出我們可以用棧做什麼？彈出操作讀取頂部符號並將其從棧中刪除，推送操作將指定的符號寫入棧的頂部，例如 push(X) 表示將 X 放置在棧的頂部，nop 操作對棧不做任何操作。棧符號不同於輸入磁帶上使用的“語言”字母表。我們從… 閱讀更多

上下文相關語法，其產生式具有以下形式αAβ → αγβ其中 α, β ∈ (N ∪ T)*, A ∈ N; γ ∈ (N ∪ T)+，並且如果起始符號 S 不出現在任何規則的右側，則允許規則 S → λ。這種語法生成的語言稱為上下文相關語言。每個上下文無關語法也是上下文相關的 =⇒ 上下文無關語言是上下文相關語言的子集（參見喬姆斯基正規化）。但是，並非每個上下文相關語言都是上下文無關的。示例語言 {anbncn, n > 1} 是上下文相關的，但不是上下文無關的。一個… 閱讀更多

正則語法是指每個產生式都採用以下受限形式之一的語法 -B → ∧, B → w, B → A, B → wA。（其中 A、B 是非終結符，w 是非空終結符字串。）正則語法的限制每個產生式的右側只能出現一個非終結符。非終結符必須出現在右側的最右邊。因此，產生式如下 -A → aBc 和 S → TU這些不是正則語法的一部分，但產生式 A → abcA 是。像 A → aB|cC 這樣的內容是允許的，因為它們實際上… 閱讀更多