プッシュダウン・オートマトン

オートマトン理論

プッシュダウン・オートマトン（テンプレート:Lang-en-short）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。

ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。

概要

プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。

1. スタックのトップを使って成すべき状態遷移を判断する。
2. 遷移実行の一部としてスタック操作を行うことが出来る。

プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。プッシュダウン・オートマトンはスタックを遷移先選択のパラメータに加える。つまり、入力信号と現在状態とスタックのトップにある文字から遷移先を選択する。

プッシュダウン・オートマトンは、遷移を実行する動作の一部としてスタックを操作することもできる。通常の有限オートマトンは遷移の結果として新しい状態を選択する。スタック操作とはある特定の文字をスタックにプッシュすることやスタックのトップをポップすることを意味する。また、プッシュダウン・オートマトンはスタックを操作せずにそのままにしておくこともできる。どう操作するかは状態遷移表によって決定される。

まとめると、入力信号と現在状態とスタック上の文字によって状態遷移すると共に、必要に応じてスタック操作を行う。

有限オートマトンでも特に非決定性有限オートマトンに基づいている場合、「非決定性プッシュダウン・オートマトン」（NPDA、nondeterministic pushdown automaton）と呼ばれる。決定性有限オートマトンに基づいている場合、「テンプレート:仮リンク」（DPDA、deterministic pushdown automaton）と呼ばれる。非決定性とは、入力信号と状態とスタック上の文字を与えられても次の遷移先が一意に決定されない場合があることを意味する。

有限オートマトンにふたつのスタックを接続することもでき、これは事実上チューリングマシンと等価な非常に強力なデバイスとなる。線形拘束オートマトンはプッシュダウン・オートマトンよりも強力だが、チューリングマシンよりは非力である。

形式的定義

形式的には、PDA は以下の6-タプルで定義される。

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F)$

ここで、

• $Q$ は状態の有限集合
• $\mathrm{\Sigma }$ は入力アルファベットの有限集合
• $\mathrm{\Gamma }$ はスタック上のアルファベットの有限集合
• $\delta$: $Q\times {\mathrm{\Sigma }}_{ϵ}\times {\mathrm{\Gamma }}_{ϵ}⟶P(Q\times {\mathrm{\Gamma }}_{ϵ})$ は遷移関数
• $q_0$ は開始状態
• $F\subset Q$ は受容（受理）状態の集合
• ${\mathrm{\Gamma }}_{ϵ}=\mathrm{\Gamma }\cup \{ϵ\}$
• ${\mathrm{\Sigma }}_{ϵ}=\mathrm{\Sigma }\cup \{ϵ\}$

計算定義 1

任意のPDA、$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F)$ について、計算経路の順序は (n+1)-タプル $(q_0,q_1,....,q_n)$ で表され（ここで $q_i\in Q,n\ge$ 0 ）、以下の条件が成り立つ。

1. $i=0,1,2,\dots ,n-1$ について、$(q_{i+1},b_{i+1})\in \delta (q_i,w_{i+1},a_{i+1})$
   ここで $w_{i+1}\in {\mathrm{\Sigma }}_{ϵ},a_{i+1},b_{i+1}\in {\mathrm{\Gamma }}_{ϵ}$
2. $\mathrm{\exists }{s}_0,s_1,s_2,s_3,\dots ,s_n\in {\mathrm{\Gamma }}^{*}$ について$s_i=a_{i+1}{t}_i,s_{i+1}=b_{i+1}{t}_i,t_i\in {\mathrm{\Gamma }}^{*}$

直観的に、PDA での計算の任意の時点で、スタックのトップから記号を読み取ってそれを他の記号に置換するか、置換せずに単にスタックのトップを削除するか、あるいは読み取らずにスタックに新たに記号を追加するか、なにもしないかという選択肢がある。これらは連立方程式 $s_i=a_{i+1}{t}_{i}and{s}_{i+1}=b_{i+1}{t}_i$で制御される。$s_i$ は、(i+1)番目の状態遷移の直前のスタックの内容であり、$a_{i+1}$ はスタックのトップから除去される記号である。$s_{i+1}$ は (i+1)番目の状態遷移の直後のスタックの内容であり、$b_{i+1}$は (i+1)番目の状態遷移に伴ってスタックに追加される記号である。

$a_{i+1}$ も $b_{i+1}$ も $ϵ$ の可能性もある。

• $a_{i+1}\ne ϵ$ かつ $b_{i+1}\ne ϵ$ なら、PDA はスタックから記号を読み取り、それを別の記号に置換する。
• $a_{i+1}\ne ϵ$ かつ $b_{i+1}=ϵ$ なら、PDA はスタックから記号を読み取り、単にそれを削除する。
• $a_{i+1}=ϵ$ かつ $b_{i+1}\ne ϵ$ なら、PDA は単に記号をスタックに追加する。
• $a_{i+1}=ϵ$ かつ $b_{i+1}=ϵ$ なら、PDA はスタックを更新しない。

$n=0$ の場合、計算経路はシングルトンとなる$(q_0)$。

計算定義 2

任意の入力$w=w_1{w}_2\dots w_m$ について、$w_i\in \mathrm{\Sigma },m\ge 0$ であり、M が w を受容するのは、計算経路 $(q_0,q_1,....,q_n)$ と有限の状態列 $r_0,r_1,r_2,\dots ,r_m\in Q,m\le n$が存在し、以下が成り立つ場合である。

1. $i=0,1,2,\dots ,m$ の各々について、$r_i$ が計算経路上にある。すなわち、
   ある$f(i)$ が存在し、$i\le f(i)\le n$で、$r_i=q_{f(i)}$ が成り立つ。
2. $i=0,1,2,\dots ,m-1$ の各々について、$(q_{f(i)+1},b_{f(i)+1})\in \delta (r_i,w_{i+1},a_{f(i)+1})$
   ここで $a_{f(i)+1}$ と $b_{f(i)+1}$ は計算定義 1 で定義されたもの。
3. $q_j\notin \{r_0,r_1,\dots r_m\}$ であるとき、$(q_{j+1},b_{j+1})\in \delta (q_j,ϵ,a_{j+1})$
   ここで $a_{j+1}$ と $b_{j+1}$ は計算定義 1 で定義されたもの。
4. $r_m=q_n$ かつ $r_m\in F$

これら定義はスタックが空かどうかの判定機構を提供していない点に注意。スタックが空かどうかを判定するには、計算前にスタックに特殊記号を書いておき、PDA がスタックを読んでその記号が読み取れた場合は空であると判断する。形式的には、$\delta (q_0,ϵ,ϵ)=\{(q_1,\mathrm{\$})\}$ という遷移を導入する。ここで、$ はその特殊記号である。

例

言語 $\{0^n{1}^n|n\ge 0\}$ を認識するPDAの形式定義は以下の通りである。

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_1,F)$

$Q=\{q_1,q_2,q_3,q_4\}$

$\mathrm{\Sigma }=\{0,1\}$

$\mathrm{\Gamma }=\{0,\mathrm{\$}\}$

$F=\{q_1,q_4\}$

$\delta (q_1,ϵ,ϵ)=\{(q_2,\mathrm{\$}),(q_1,ϵ)\}$

$\delta (q_2,0,ϵ)=\{(q_2,0)\}$

$\delta (q_2,1,0)=\{(q_3,ϵ)\}$

$\delta (q_3,1,0)=\{(q_3,ϵ)\}$

$\delta (q_3,ϵ,\mathrm{\$})=\{(q_4,ϵ)\}$

上記以外の状態、入力、スタック記号については常に $\delta (q,w,a)=\mathrm{\Phi }$ である。

参考文献

• テンプレート:Cite book Section 2.2: Pushdown Automata, pp.101–114.

関連項目

• スタックマシン
• 文脈自由文法
• 有限オートマトン

外部リンク

• non-deterministic pushdown automaton on Planet Math.
• JFLAP - 数種類のオートマトンのシミュレータ。非決定性プッシュダウンオートマトンも含まれている。