# Pushdown Automata / PDA

跟 NFA 有點像，但多了 stack 這個物件來幫我們記錄更多東西，也讓我們可以辨識一些不正常語言。

Pushdown Automata 跟 CFG 的 power 是等價的，或者說他們的能力是一樣的。

這給了我們方便的判斷， 因為如果我們想要證明某個語言是 CFL，則我們要嘛建構出一個 Pushdown Automata，要嘛產生出一個 CFG。

當然，有些語言比較容易由 CFG 描述，有些則是 Pushdown Automata。

## PDA 的 stack

他就是個 stack，必須符合先進後出的規則；寫入是 push，寫出是 pop，每次寫入一個 symbol。

堆疊的好用之處在於，它可以幫我們記住「無限的資訊」，因為堆疊沒有容量限制，所以對於 $\{0^{n}1^{n}|n\ge0\}$ 這種語言，就可以用 PDA 來辨識。

:::warning
每次讀到 0，就塞一個 0 到堆疊；每次讀到 1 ，就從堆疊吐一個 0 出來：
- 如果讀完 input 後堆疊是空的，允許該字串
- 如果以下條件滿足，則拒絕該字串
- 堆疊是空的，但是卻讀到了 1
- 堆疊存有 0，但是卻讀完了字串
- 讀入的字串中，兩個以上的 0 後面都跟隨著一個以上的 1
- 像是 0101
:::

# Deterministic 跟 Nondeterministic

跟有限自動機一樣， PDA 也有分這兩種，也就是讀到一個 input 後是一種輸出狀態或是多種輸出狀態。

但是要注意，DPDA 跟 NDPA 的 Power 不一樣，他們能力有所不同，而只有 NPDA 跟 CFG 的能力是一樣的，所以下面我們就只介紹 NPDA，**下面提到的 PDA 都是指 NPDA**。

:::warning
之前有提到 NFA 跟 DFA 是等價的，因為他們之間可以進行轉換，但是 NPDA 跟 DPDA 就不是等價的，有些語言只有 NPDA 可以辨識，但是 DPDA 不行。
:::

# NPDA 標準定義

一個 NPDA 是個 6 tuple：

$$
(Q,\Sigma,\Gamma,\delta,q_0,F)
$$

1. $Q$ 是狀態的集合
2. $\Sigma$ 是 input 的字母集合
3. $\Gamma$ 是 stack 的字母集合
4. $\delta：Q\times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon}\rightarrow \mathcal{P}({Q\times \Gamma_{\varepsilon}})$ 是轉換函數
5. $q_0\in Q$ 是起始狀態
6. $F\subseteq Q$ 是允許狀態們

- 因為 stack 會存放字母，所以有其專門的代號 $\Gamma$。
- 所以也會有包含空字串的代號形式：
- $\Sigma_{\varepsilon}=\Sigma\cup\{\varepsilon\},\ \Gamma_{\varepsilon}=\Gamma\cup\{\varepsilon\},$
- 轉換函數的定義域是 $Q\times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon}$
- $\Gamma_{\varepsilon}$ 的部分是當前 stack 的 top
- $\Sigma_{\varepsilon}$ 的部分是當前的 input
- $\varepsilon$ 的行為請見下面
- 轉換函數的值域是 $\mathcal{P}({Q\times \Gamma_{\varepsilon}})$
- 轉換函數的一個輸出，告訴 NPDA 下一步要移動到哪個狀態，以及在 stack 上寫入哪個字元，也就是 ${Q\times \Gamma_{\varepsilon}}$
- 但因為是 Nondeterministic，所以可以有很多種輸出，才因此是 Power set

## 允許一個字串

如果 NPDA 允許一個字串：

- 令允許字串為 $w=w_{1}w_{2}...w_{m},w_{i}\in\Sigma_{\varepsilon}$
- 與其對應的狀態是 $q_{0},q_{1},...,q_{m}\in Q$
- 以及對應每個狀態當下，堆疊中存放的字串 $s_{0},s_{1},...,s_{m}\in \Gamma_{\varepsilon}^{*}$
- 注意，每個 $s_{i}$ 都是字串

要滿足下面三個條件：

- $r_{0}=q_{0}$ 也就是第一個狀態要是起始狀態
- $s_{0}=\varepsilon$ 也就是一開始堆疊內要是空的
- 對於 $i=0,...,m-1$，$(r_{i+1},b)\in\delta(r_{i},w_{i+1},a)$
- 其中 a 跟 b 分別代表讀入前後 top 的 symbol
- 並且 $s_{i}=at,s_{i+1}=bt,t\in\Gamma^{*}$
- 這告訴我們這個 NPDA 正確的按照當前狀態、當前堆疊以及下一個 input symbol 的內容進行移動
- $r_{m}\in F$ 也就是最後一停在允許狀態的集合

:::warning
畫成狀態圖的時候，會在箭頭旁邊寫上 $a,b\rightarrow c$ 來表示

$$
\Huge
\overset{a,b\rightarrow c}{\longrightarrow}
$$

- $a$ 一樣是當前讀到的 symbol
- $b\rightarrow c$ 則代表 top 從 $b$ 變成了 $c$
- 也就是讀取 $b$ 之後 pop 掉 $b$，並再把 $c$ 寫入。
:::

## 空字串的行為

如果輸入的 top 是空字串，其意義是「不讀取 top」。

而這三個 symbol 都可以為空字串：
- $a=\varepsilon$ 代表不讀入任何 input 就往下一個狀態邁進
- $b=\varepsilon$ 代表不讀取 top 也不做 pop，直接寫入 $c$
- $c=\varepsilon$ 代表讀取 top 並做 pop 後，不寫入任何 symbol

## 注意事項

正式的 PDA 定義中，我們沒有明確的機制來檢驗當前堆疊是否為空，但是我們可以不正式地藉由「特殊字元 $」，放到堆疊內，這樣只要之後再看到 $ 出現在堆疊內，代表堆疊已經空了。

例如下面就是 $\{0^{n}1^{n}|n\ge0\}$ 這種語言的 NPDA，可以看到我們在起始狀態 $q_1$ 無條件的塞入 \$ 符號

>我忘記畫指向起始狀態的箭頭了

同樣的正式的 PDA 定義中也無法確認是否到輸入的結尾了，但是上圖的 PDA 可以做到，因為我們多加了 \$ 之後，結束時的判斷也跟 \$ 有關，要走到 $q_4$ 的前提是堆疊內只剩下 \$，否則永遠到不了。

:::info
可以注意到堆疊先進後出的約束在此發揮了作用
:::

# 例子1

$$
{a^ib^jc^k\ |\ i, j, k ≥ 0\ and\ i = j\ or\ i = k}
$$
>注意，這跟之前那個本質上混淆的語言 $\{a^{i}b^{j}c^{k}\ |\ i=j\ or\ j=k\}$ 不一樣


- 我們要檢查的是 a 跟 b 或 c 的數量有沒有一樣，所以堆疊內存放的是 a，也就是 $q_2$ 在做的事情。
- 此時存完後會無條件分出兩支，可以看到都是 $ε,ε\rightarrow ε$
- 上路是在檢查 a 跟 b，如果到了允許狀態，還要記得後面可能會有 c，也就是 $q_4$ 的 $c,ε\rightarrow ε$
- 下路首先要把 b 給抽乾，所以才會先經過 $q_5$

:::warning
可以注意到 $q_2,q_3,q_5,q_6$ 他們的結構都是一個指向自己的箭頭，搭配 $ε,ε\rightarrow ε$，這代表說這幾個狀態「隨時都會去猜」當前有沒有可能要進入下一個狀態。

以 $q_2$ 來說就是隨時都會去猜 a 讀完了沒。
:::

# 例子2

這次的語言是：

$$
\{ww^{\mathcal{R}}\ |\ w\in\{0,1\}^{*}\}
$$


一樣可以看到 $q_2$ 會隨時去「猜」到 $q_3$ 了沒，也就是到了 $w$ 跟 $w^{\mathcal{R}}$ 的交界處了沒。

:::warning
可以注意到，因為現在從某個狀態到下一個狀態會由三個值決定，所以更好的表達我們想要的結果。
例如在 $q_3$ 指向自己的箭頭中， $0, 0\rightarrow \varepsilon$ 必須要求除了讀到 0，還要求top 也要是 0，因此只要 top 不是 0 的話就會被判定是不允許的輸入。
:::

---

# PDA 跟 CFG 的等價

接下來我們要證明 PDA 跟 CFG 具有相同的力量；跟之前證明 NFA 和 DFA 一樣，我們要嘗試從 PDA 轉換回 CFG，還有從 CFG 轉換回 PDA。
>別忘記這裡的 PDA 是指 NPDA。

總之我們要嘗試證明：

:::info
一個語言是「context free」，若且為若某些 PDA 辨識這個語言
:::

# 左到右

:::warning
如果一個語言是「context free」，則某些 PDA 辨識這個語言。
:::

先宣告變數：

- A 是內容自由的語言
- G 是 A 的文法

接著要嘗試從 G 轉換成一個等價的 PDA，我們叫他 P。

我們現在要做的事情是，我們想要創建一個 PDA 可以模擬「G產生出某個字串的過程」。

因為「G」是一個文法，他可以有各式各樣的 derivation，一般來說很難去判斷到底某個字串能不能從起始變數來得到，但是 NPDA 因為其 Nondeterministical 的特性，讓他可以去猜各種無限的可能，因此可以來模擬 G 生成某個字串的過程。

## 猜的方法

首先在起始狀態時，將起始變數 A 放進 stack 後進入一個「循環狀態」，這個循環狀態會去看 top 內容是甚麼來決定下一步。

因為一開始就放進起始變數，所以我們可以知道此時「top 是一個變數」，接著我們根據 G ，將起始變數替換成其他內容：

$$
A\rightarrow w,\ w\in (V_G\cup \Sigma_G)^{*}
$$

所以就只要把 top 內的起始變數替換成 w 就行；而可能有很多種這樣的規則，這剛好就是 PDA 可以去「無限的猜」的部分。

假如**有某條分枝將 A 替換成了一個終端 a**：

$$
A\rightarrow a
$$

此時 top 變成了 a，下一次讀到的 top 就是一個終端，這時就只要將 a 跟讀入的字串進行比對就可以。

如果剛好我們讀到的字串就只有 a，我們就可以將 a 從 stack 移除，這樣一來 stack 內就空了，也就代表我們讀入的字串確實可以由 G 所產生，所以就可以進入允許狀態。

上面就是我們使用 PDA 來去「模擬」G 產生某個字串的過程。

## P 的結構

1. 首先，先將 $ 跟起始變數放進 stack
2. 重複下面流程
- 如果 top 是一個變數 A，nondeterministically 的選擇一個可以特換掉 A 的規則
- 如果 top 是一個終端，不對 stack 做任何操作，只單純讀入一個 input 做比對。
- 如果 top 是 $，進入允許狀態；也就是代表我們讀完並允許該字串。

### 替換變數的方法

上面有提到如果 top 是一個變數 A，PDA 要找出一個可以替換掉 A 的規則替換掉他，至於所謂的替換，就是把 $A\rightarrow w$ 的右手邊寫入 stack。

並且要注意，要注意填入 stack 的順序，像是 $A\rightarrow BC$ 的話 B 就要最後放進 stack，實際放的時候如下：

$$
\varepsilon, A \rightarrow C\\
\varepsilon, \varepsilon \rightarrow B\\
$$

也就是說在 PDA 中會存在：

- $\delta(q_i,\varepsilon,A)=(q_{i+1},C)$
- $\delta(q_i+1,\varepsilon,C)=(q_{i+2},B)$

但是這樣寫的話有點麻煩，所以通常我們會用一個簡單的表示法簡寫成：

$$
\delta(q_i,\varepsilon,A)=(q_{i+1},BC)
$$

## 詳細建構式證明


上面是我們根據 G 所模擬出的 PDA。

$$
P=(Q,\Sigma,\Gamma,\delta,q_{start},F)\\
Q = \{q_{start},q_{loop},q_{accept}\}
$$

起始狀態是 $q_{start}$，唯一的允許狀態是 $q_{accept}$。

轉換函數的部分有兩個步驟：

- 首先先將$ 跟起始變數塞入 stack：

$$
\delta(q_{start},\varepsilon,\varepsilon)=(q_{loop},S$)
$$

- 接著是迴圈的部分
- 如果 top 是變數 A，並且有某個規則 $A→w$，$w$ 是由變數跟終端組成的字串
- $$\delta(q_{loop},\varepsilon,A)=(q_{loop},w)$$
- 如果 top 是終端 a
- $$\delta(q_{loop},a,a)=(q_{loop},ε)$$
- 如果 top 是 $
- $$\delta(q_{loop},ε,$)=(q_{accpet},ε)$$

## 例子

假如我們手上有一個文法 G：

$$
S\rightarrow aTb\ |\ b\\\
T\rightarrow Ta\ |\ \varepsilon\\
$$


記住實際畫出來時，塞字串到 stack 的話還是要一個一個塞。

---

# 右到左

:::warning
如果一個 PDA 辨識某個語言，則該語言是「context free」。
:::

先宣告變數：

- $P$ 是我們的 PDA

這時候換成我們要用某個文法 G，來模擬某個 PDA 的行為；PDA 所生產的所有字串，這個文法 G 也都要可以產生出來。

## 核心概念

我們會讓文法有這樣的一個變數：

$$
A_{pq}
$$

這個變數可以產生出所有的字串，而這些字串可以使 $P$ 從狀態 $p$ 移動到狀態 $q$，並且「開始時跟結束時 stack 的狀態是一樣的」
> 也就是說進入 $p$ 以及之後，我們會在 stack 塞入一些內容，但是當我們到了 $q$ 的時候，那些塞入 stack 的內容又會被我們吐出來

有了 $A_{pq}$ 這個變數後，接著是定義其相關的規則，並且這些規則真的可以讓 $A_{pq}$ 產生出使 $P$ 從狀態 $p$ 移動到狀態 $q$，並且「開始時跟結束時 stack 的狀態是一樣的」的字串

## 修改結構

為了讓推導過程比較輕鬆，我們將 PDA 轉換成另一種等價的形式：

1. PDA 只有一個允許狀態 $q_{accept}$
2. 在進到允許狀態時 stack 會是空的
3. 每個 transition 要嘛是 push 一個字元，要嘛是 pop 一個字元，但是不可以都不做或同時做

第 1 點很簡單，就是把所有的允許狀態都拉一條空字串箭頭指向同一個新允許狀態 $q_{accept}$ 就好。

$$
ε, ε\rightarrow ε
$$

第 2 點也很簡單，就是多加幾個狀態把 stack 內容一個一個清掉

$$
ε, a\rightarrow ε
$$

然後不要忘記我們要新增自己的起始狀態 $q_{\text{my start}}$ 跟允許狀態 $q_{\text{my accept}}$來取代原本的起始狀態跟上面的 $q_{accept}$，因為要加入錢錢來判斷起始跟結束：

$$
ε, ε\rightarrow $\\
ε, $\rightarrow ε\\
$$

第 3 點其實也蠻容易的：

- 如果有個 transition 為 $a,b\rightarrow c$
- 將他拆解成：$a,b\rightarrow ε$ 跟 $ε,ε\rightarrow c$
- 如果有個 transition 為 $a,ε\rightarrow ε$
- 將他拆解成：$a,ε\rightarrow b$ 跟 $ε,b\rightarrow c$

## P 的運作過程

而對於這樣修改過的 P，我們來看看他運行的過程。對於任何 P 允許的字串 $x$，撇除 $ 符號不談：

- P 計算 $x$ 的第一步一定是一個 push，因為我們有定義每一步(each transition) 都一定有 push 或 pop，而一開始 stack 是空的，所以一定是 push。
- 而最後 stack 會是空的，所以可以知道計算 $x$ 的最後一步一定是 pop。

此時我們可以遇到兩種情形

- 情形一：開頭 push 跟結尾 pop 的字元是同一個字元
- 因此可以知道 stack 在計算 $x$ 的過程中絕對不可能會變成空的
- 此時我們可以下 $A_{pq}\rightarrow aA_{rs}b$ 這樣的規則，這樣我們的文法就可以「稍為的」產生該字串的一部份
- 情形二：開頭 push 跟結尾 pop 的字元是不同一個字元
- 因此可以知道 stack 在計算 $x$ 的過程中有某些時候變成了空的
- 此時我們可以用 $A_{pq}\rightarrow A_{pr}A_{rq}$ 這樣的規則來模擬 P 的行為
- $r$ 是第一個 stack 變成空的的狀態

:::warning
所以這時候回顧為甚麼我們定義變數的方式如此特別，因為在修改過的 PDA 上，讀到一個字串時，**他的 stack 高度就像是一群山峰**，起始是空的結束時也是空的，中間可能有許多山谷，山谷可能不會到最底，也有可能到最底，詳細可以看下面的圖。

因此對於一個 PDA 允許的字串，我們可以把這些山峰切很多個水平刀，最底層的水平刀就是 $A_{q_0,q_{accept}}$，因為每個字串的 stack 起始是空的，結束時也是空的。

接著對於某個字串，如果他是情形一，則可以從 $A_{q_0,q_{accept}}$ 根據 PDA 的轉移函數，往上一點的高度再切一個水平刀，得到 $aA_{q_{i},q_{j}}b$，此時我們就把情形從原本的 $A_{q_0,q_{accept}}$ 遞迴到了子情形 $A_{q_{i},q_{j}}$。

而這種切法因為是根據原本的 PDA 的轉移函數所制定的，**所以只有這條規則將我們建立的文法跟實際要模擬的 PDA 建立起了連結。**

至於情形二，就是將原本的情形拆成兩個子情形。
:::

## 建構

先宣告我們的 P 形式如下

$$
P=(Q,\Sigma,\Gamma,\delta,q_{0},F=\{q_{accept}\})\\
$$

而我們建構的 $G$ 如下：

$$
G=(V_G,\Sigma_G,R_G,S_G)\\
V_G=\{A_{pq}|p,q\in Q\}\\
S_G=A_{q0,q_{accept}}
$$

並且 $G$ 的規則 $R_G$ 如下，有三種情形：

### 情形一：連結情形

- 對於每個 $p,q,r,s\in Q,\ u\in \Gamma,\ a,b\in \Sigma_{ε}$，如果
- $\delta(p,a,ε)$ 得到的狀態中含有 $(r,u)$
- $\delta(s,b,u)$ 得到的狀態中含有 $(q,ε)$
- 則加入 $A_{pq}\rightarrow aA_{rs}b$ 這條規則
- 要小心，這裡加入的 $u$ 只會是「那個獨一無二的 $u$」，而不是跟 $u$ 一樣的字元就好

這種情形是我們所模擬的文法可以「跑起來」的根基，因為**只有這種規則跟實際 PDA 運行的過程有所連結**。

### 情形二：拆解情形

- 對於每個 $p,q,r\in Q,\ u\in \Gamma,\ a,b\in \Sigma_{ε}$：
- 加入 $A_{pq}\rightarrow A_{pr}A_{rq}$ 這條規則

這條規則代表說，由 $A_{pq}$ 產生的字串可以由 $A_{pr}$ 跟 $A_{rq}$ 兩種變數所產生的字串給「拼湊起來」。
**但是要注意，這裡為了方便性，是將全部可以拆解的可能的規則都加了進去，但實際上有些規則可能 PDA 根本不會發生**，也就是說這些加入的規則中會有一些冗員，詳細情形可以見[維基百科](https://en.wikipedia.org/wiki/Context-free_grammar#Decidable_problems)。

### 情形三：末端情形

- 對所有的 $p\in Q$
- 加入 $A_{pp}\rightarrow ε$

這個是屬於遞迴中的 terminal step，也就是何時停下來的那個「停下來」。對於某個字串，當他的 stack 山峰走到尖端的時候，令他讀 $a$ 後塞入 $u$ 走到尖端，讀到 $b$ 後吐出 $u$ 離開尖端；

此時令尖端左側、尖端，跟尖端右側的狀態分別為 $A$、$B$ 跟 $C$，由於這個是被 PDA 所允許，因此可以知道 PDA 具有 $\delta(A,a,\varepsilon)=(B,u)$ 跟 $\delta(B,b,u)=(C,\varepsilon)$ 這兩個轉移函數，而我們構建的文法就會因為這兩個規則而制定出 $A_{AC}\rightarrow aA_{BB}b$，這時就出現了末端情形 $A_{BB}$。

這也是為甚麼我們會讓 $A_{BB}\rightarrow ε$，因為跟實際字串運算有聯結的部分，我們都留給了情形一，因此末端情形可以安心的負責終結掉文法的 derivation 操作就好。

## 山峰圖示


上面這張圖對應的是情形一，可以看到 $r$ 跟 $s$ 中間的連線就是上面所提及的第二刀。


上面這張圖對應的是情形二，此時可以將這種字串由兩種變數產生的結果串聯起來。

# 證明

建構好 $G$ 的規則後，接著要證明「$A_{pq}$ 產生字串 $x$」若且唯若「$x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持起始跟結束時 stack 狀態一樣」

下面我們都會用歸納法來證明；為了方便說明，下面我會將「保持起始跟結束時 stack 狀態一樣」簡稱為「保持不變」。

## 左到右

如果 $A_{pq}$ 產生字串 $x$，則 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持起始跟結束時 stack 狀態一樣。

我們的歸納法是以「derivation 的步數」，或者說「從 $A_{pq}$ derive 出 $x$ 的步數」作為歸納的骨牌。

- Base case：derivation 只有 1 步
- 「如果 $A_{pq}$ derive 出 $x$ 只有 1 步時，則 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持 stack 不變」。這是我們要推導的。
- 如果只花一步的替換就得到結果字串，那麼具有這種性質的變數只會是那一種，就是 $A_{pp}\rightarrow ε$ 的這種規則；所以如果當我們由 $A_{pp}$ 產生了 $ε$，我們要證明 $ε$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持 stack 不變
- 而 $ε$ 字串確實可以讓 $P$ 從 $p$ 走到 $p$ 並保持 stack 不變，因為你可以對任何狀態加入指向自己的空字串，並且不改變 stack 內容
- Induction step：已知「如果從 $A_{pq} \overset{*}{\Rightarrow} x$ 只有 k 步，則 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持 stack 不變」，接著要推導「如果從 $A_{pq} \overset{*}{\Rightarrow} x$ 只有 k+1 步，則 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持 stack 不變」
- 如果 $A_{pq} \overset{*}{\Rightarrow} x$ 只需要 k+1 步，第一步一定要嘛是 $A_{pq} \rightarrow aA_{rs}b$ 或 $A_{pq} \rightarrow A_{pr}A_{rq}$
- 如果第一步是 $A_{pq} \rightarrow aA_{rs}b$，令 $A_{rs}$ 產生的字串叫 $y$，則產生的字串可以寫為 $ayb$
- 因為 $A_{rs}$ 步數是 k，所以歸納法告訴我們 $P$ 從 $r$ 走到 $s$ 可以保持不變
- 而 $A_{pq} \rightarrow aA_{rs}b$ 根據上面建構時的定義，可以知道在那兩個轉移函數就是先塞入一個 $u$ 到 stack，然後接著以保持不變的方式產生出 y，最後又從 stack 吐出 $u$。
- 因此我們可以知道 $P$ 從 $p$ 走到 $q$ 可以保持不變。
- 如果第一步是 $A_{pq} \rightarrow A_{pr}A_{rq}$，令 $A_{pr}$ 產生的字串叫 $y$，$A_{rq}$ 產生的字串叫 $z$
- 因為 $A_{pr}$ 跟 $A_{rq}$ 的步數都小於等於 k，所以可以知道：
- $P$ 從 $p$ 走到 $r$ 可以保持不變
- $P$ 從 $r$ 走到 $q$ 可以保持不變
- 所以 $P$ 可以從 $p$ 走到 $q$ 保持不變
- 這樣就完備了 Induction step，也就是說對所有的 derivation 次數，只要 $A_{pq}$ 產生字串 $x$，則 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持不變。

## 右到左

如果 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持不變，則 $A_{pq}$ 產生字串 $x$

我們的歸納法是以「Computation 的次數」，或者說「$P$ 計算 $x$ 所需的次數」作為歸納的骨牌。

- Base case：「如果只計算 0 次並保持不變，則 $A_{pq}$ 產生字串 $x$」
- 所以我們要從「計算 0 次並保持不變」證明出「$A_{pq}$ 產生字串 $x$」
- 如果只計算 0 次，那只會是 $\varepsilon$；並且起始跟結束狀態相同。
- 我們有定義 $A_{pp} \rightarrow \varepsilon$，所以 Base case 成立
- Induction step：已知「如果只計算 k 次並保持不變，則 $A_{pq}$ 產生字串 $x$」，接著要推導「如果只計算 k+1 次並保持不變，則 $A_{pq}$ 產生字串 $x$」
- 第一種情形，第一次 push 的跟最後一次 pop 的是相同的字元
- 令第一次輸入為 $a$，最後一次輸入為 $b$，中間字串為 $y$；$x=ayb$
- 令那個相同的字元為 $u$
- 因為 $x$ 讓 $P$ 從 $p$ 走到 $q$ 並保持不變，i.e. 我們具有 $\delta(p,a,ε)=(r,u)$ 跟 $\delta(s,b,u)=(q,ε)$，因此我們建構文法時會建構出 $A_{pq}\rightarrow aA_{rs}b$；i.e.
- 因為 $y$ 需要的計算次數為 k 次，根據已知歸納結果，$A_{rs}$ 產生字串 $y$
- 所以我們可以知道 $A_{pq}$ 確實會產生出 $x$，$A\overset{*}{\Rightarrow}x$
- 第二種情形，第一次 push 的跟最後一次 pop 的是不相同的字元
- 此時令 $x=yz$，$x$ 到 $y$ 到 $z$ 分別經過 $p$、$r$ 跟 $q$三個狀態
- 因為 $y$ 跟 $z$ 計算次數都小於等於 k，根據已知歸納結果，$A_{pr}$ 跟 $A_{rq}$ 會產生出 $y$ 跟 $z$
- 而 $A_{pq}\rightarrow A_{pr}A_{rq}$ 這條規則在建構文法時有被加到規則裡，所以由上所述可以知道 $A_{pq}$ 確實會產生出 $x$，$A\overset{*}{\Rightarrow}x$
- 這樣就完備了 Induction Step，也就是說對於所有計算 $x$ 次數 k，只要 $x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持不變，則 $A_{pq}$ 產生字串 $x$。

## 總結

這樣一來我們就成功證明 「$A_{pq}$ 產生字串 $x$」若且唯若「$x$ 可以讓 $P$ 從 $p$ 走到 $q$ 並保持起始跟結束時 stack 狀態一樣。

而所有 PDA 的字串都可以讓 $P$ 從 $q_0$ 走到 $q_{accept}$ 並保持起始跟結束時 stack 狀態一樣，因此可知$A_{q_{0},q_{accept}}$ 會產生所有 PDA 允許的字串