プッシュダウン・オートマトン
プッシュダウン・オートマトン(Pushdown Automaton)は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。
ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。
, s n ∈ Γ ∗ {\displaystyle \exists \,s_{0},\,s_{1},\,s_{2},\,s_{3},\,\dots ,\,s_{n}\,\in \Gamma ^{*}} について s i = a i + 1 t i , s i + 1 = b i + 1 t i , t i ∈ Γ ∗ {\displaystyle s_{i}=a_{i+1}t_{i},\,s_{i+1}=b_{i+1}t_{i},\,t_{i}\in \Gamma ^{*}}
直観的に、PDA での計算の任意の時点で、スタックのトップから記号を読み取ってそれを他の記号に置換するか、置換せずに単にスタックのトップを削除するか、あるいは読み取らずにスタックに新たに記号を追加するか、なにもしないかという選択肢がある。これらは連立方程式 s i = a i + 1 t i a n d s i + 1 = b i + 1 t i {\displaystyle s_{i}=a_{i+1}t_{i}\,and\,s_{i+1}=b_{i+1}t_{i}} で制御される。 s i {\displaystyle \,s_{i}} は、(i+1)番目の状態遷移の直前のスタックの内容であり、 a i + 1 {\displaystyle a_{i+1}} はスタックのトップから除去される記号である。 s i + 1 {\displaystyle s_{i+1}} は (i+1)番目の状態遷移の直後のスタックの内容であり、 b i + 1 {\displaystyle b_{i+1}} は (i+1)番目の状態遷移に伴ってスタックに追加される記号である。
任意の入力 w = w 1 w 2 ... w m {\displaystyle w=w_{1}w_{2}\dots w_{m}} について、 w i ∈ Σ , m ≥ 0 {\displaystyle w_{i}\in \Sigma ,m\geq 0} であり、M が w を受容するのは、計算経路 ( q 0 , q 1 , . . . . , q n ) {\displaystyle (q_{0},\,q_{1},....,\,q_{n})} と有限の状態列 r 0 , r 1 , r 2 , ... , r m ∈ Q , m ≤ n {\displaystyle r_{0},r_{1},r_{2},\dots ,r_{m}\in Q,m\leq n} が存在し、以下が成り立つ場合である。
i = 0 , 1 , 2 , ... , m {\displaystyle i=0,1,2,\dots ,m} の各々について、 r i {\displaystyle r_{i}} が計算経路上にある。