下推自動機 (PDA) 可以形式化地描述為七元組 (Q, Σ, S, δ, q0, I, F)，其中：Q 是有限數量的狀態；Σ 是輸入字母表；S 是棧符號；Δ 是轉移函式：Q × (Σ∪{e}) × S → Q × S；q0 是初始狀態 (q0 ∈ Q)；I 是初始棧頂符號；F 是接受狀態集 (F ∈ Q)。問題：為 0n1m2m3n (其中 n, m≥1) 構造 PDA。解答：該語言生成的字串為：L={0123, 011223, 001233…}。1 和 3 的數量相同，2 和 1 的數量相同。給定問題的 PDA 構造… 閱讀更多

下推自動機 (PDA) 可以形式化地描述為七元組 (Q, Σ, S, δ, q0, I, F)，其中：Q 是有限數量的狀態；Σ 是輸入字母表；S 是棧符號；Δ 是轉移函式：Q × (Σ∪{e}) × S → Q × S；q0 是初始狀態 (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 是帶字母表；∑ 是輸入字母表；δ 是轉移函式：δ: Q × X → Q × X × {左移，右移}；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 這樣的內容是允許的，因為它們實際上是… 閱讀更多