Theory of Computation Chapter 7 - Pushdown Automata

（請搭配達叔的投影片一起服用）

下推自動機 (Pushdown Automata) 是一種帶有資料堆疊 (Stack) 的有限自動機。

• 可分為非確定型下推自動機 (Nondeterministic Pushdown Automata, NPDA) 和 確定型下推自動機(Deterministic Pushdown Automata, DPDA)， 兩者並不等價
• 非確定型下推自動機的表達能力和上下文無關文法是相同的，兩者都可以描述上下文無關語言
• 確定型下推自動機描述的語言是上下文無關文法的子集，但是是正規文法的超集
  

Figure 1. 一台下推自動機

Nondeterministic Pushdown Automata

• 非確定型下推自動機可以表示成一個七元組
  $⟨Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,z,F⟩$
  • $Q$ 是狀態 (states) 的集合
  • $\mathrm{\Sigma }$ 是輸入字串的符號 (input alphabet) 集合
  • $\mathrm{\Gamma }$ 是堆疊可放入的符號 (stack alphabet) 集合
  • $\delta$ 是轉移函式 (transitions)， 即
    $\delta :Q\times \mathrm{\Sigma }\to Q$
  • $q_0$ 是開始狀態 (initial state)， 即自動機在還未處理輸入的時候的狀態。每個自動機只會有一個，且
    $q_0\in Q$
  • $z$ 是堆疊起始符號 (stack start symbol)， 即自動機在還未處理輸入的時候，堆疊裡存在的一個符號，且
    $z\in \mathrm{\Gamma }$
  • $F$ 是終止狀態 (final states)， 是
    $Q$ 中的狀態的子集，即
    $F\subseteq Q$
• 非確定型下推自動機的轉移函式形式如下：
  $\delta (q_1,u,s_1)=\{(q_2,s_2)\}$
  • 意義為： 在
    $q_1$ 時，若輸入字串符號是
    $u$， 且堆疊頂端的符號是
    $s_1$ 時，就轉移狀態到
    $q_2$， 並且將
    $s_1$ 取代為
    $s_2$， 如 Fig. 2 所示
    

    Figure 2. 下推自動機的運作規則

    • 其中，
      $q_1,q_2\in Q$，
      $u\in \mathrm{\Sigma }\cup \{\lambda \}$，
      $s_1\in \mathrm{\Gamma }$，
      $s_2\in {\mathrm{\Gamma }}^{\ast }$
    • $s_2$ 允許為字串，所以可以取出一個字元後塞入一個字串到堆疊中
    • 當
      $s_1$ 為
      $\lambda$ 時，代表推入(push)
      $s_2$ 進入堆疊中
    • 當
      $s_2$ 為
      $\lambda$ 時，代表從堆疊中彈出(pop)
      $s_1$
    • 當
      $s_1,s_2$ 兩者皆為
      $\lambda$， 代表不變更堆疊狀態
    • 當
      $s_1$ 為
      $z$ 時，堆疊清空，進入停機狀態(halt)， 自此不再允許任何的狀態轉移
  • 因為是非確定型，所以允許從一個狀態轉移到另一個狀態時有多個選擇（即等號右邊是集合），也允許
    $\lambda$ 轉移
• 我們可以用 Instantaneous Descriptor(ID) 描述下推自動機在某個瞬間的狀態
  • Instantaneous Descriptor 是一個三元組
    $(q,u,s)$
    • $q$ 為該狀態機當下所在的狀態
    • $u$ 為輸入字串中還沒讀完的部份
    • $s$ 為當前堆疊中剩餘的符號串（由上至下）
  • 我們用符號
    $⊢$ 表示兩個 ID 之間的轉移，例：
    $(q_1,aabb,aaaz)⊢(q_2,abb,aaz)$
  • 多次的移轉可以直接列為一個簡短的式子，例：
    $(q_0,aaabbb,z){⊢}^{\ast }(q_f,\lambda ,z)$
• 下推自動機可以接受的語言
  • 一個輸入下推自動機的字串，若可以被自動機全部讀完，並且讀完的當下停留在
    $F$， 我們就說該自動機接受 (accepted) 這個字串，此時堆疊中的狀態如何我們並不在意
  • 反之，若是以下任一狀況發生，我們就說該自動機拒絕了 (rejected) 這個字串
    • 字串不能讀完（在中途找不到可以走的轉移函式）
    • 讀完時沒有停在
      $F$
    • 堆疊被清空了但移轉尚未結束，
  • 因此，一個下推自動機可以接受的語言可以表示為
    $L(M)=\{w:(q_0,w,z){⊢}^{\ast }(q_f,\lambda ,s)\}$

Pushdown Automata and Context-Free Languages

• 非確定型下推自動機描述的語言集合，和上下文無關文法描述的是一樣的，我們稱這個語言集合為上下文無關語言 (Context Free Language)
  • 對於所有上下文無關文法描述的語言，我們都可以找到一個非確定型下推自動機來接受這個語言，亦即每一個上下文無關文法都可以轉換成等價的非確定型下推自動機
    • 第一種轉換方法
      • 先將語法轉換為 Greibach Normal Form， 即所有規則都是
        $A\to aX$ 形式
      • 新增轉移函式
        $\delta (q_0,\lambda ,\lambda )=(q_1,S)$
      • 對於所有的產生式規則，新增轉移函式
        $\delta (q_1,a,A)=(q_1,X)$
      • 新增轉移函式
        $\delta (q_1,\lambda ,z)=(q_2,z)$， 且
        $q_2=F$
      • 此轉換法是以下推自動機模仿 leftmost derivation 的過程
    • 第二種轉換方法（如 Fig. 3 所示）
      • 不用將語法做任何轉換，所有的規則都是
        $V\to W$ 形式
      • 新增轉移函式
        $\delta (q_0,\lambda ,\lambda )=(q_1,S)$
      • 對於所有的變數，新增轉移函式
        $\delta (q_1,\lambda ,V)=(q_1,W)$
      • 對於所有的字母，新增轉移函式
        $\delta (q_1,u,u)=(q_1,\lambda )$
      • 新增轉移函式
        $\delta (q_1,\lambda ,z)=(q_2,z)$，且
        $q_2=F$
      • 這種轉換法較為迅速且方便
        

        Figure 3. 將上下文無關文法轉換成下推自動機

    • 由於所有的上下文無關文法都可以透過這兩種方式轉換成等價的下推自動機，因此上下文無關文法可描述的語言包含於下推自動機所描述的語言當中
  • 對於所有被非確定型下推自動機接受的語言，我們都可以找到一個上下文無關文法來產生這個語言，亦即每一個非確定型下推自動機都可以轉換成等價的上下文無關文法
    • 略（有空再補 Q）

Deterministic Pushdown Automata and Deterministic CFLs

結論： 確定型下推自動機的表達能力沒有非確定型的強，其可接受的語言是上下文無關語言的子集合，但是是正規語言的超集合。

Figure 4. 好像只考到這（。