プッシュダウン・オートマトン
すなわち、ある f ( i ) {\displaystyle f(i)} が存在し、 i ≤ f ( i ) ≤ n {\displaystyle i\leq f(i)\leq n} で、 r i = q f ( i ) {\displaystyle r_{i}=q_{f(i)}} が成り立つ。
i = 0 , 1 , 2 , ... , m − 1 {\displaystyle i=0,1,2,\dots ,m-1} の各々について、 ( q f ( i ) + 1 , b f ( i ) + 1 ) ∈ δ ( r i , w i + 1 , a f ( i ) + 1 ) {\displaystyle (q_{f(i)+1},b_{f(i)+1})\in \delta (r_{i},w_{i+1},a_{f(i)+1})} ここで a f ( i ) + 1 {\displaystyle a_{f(i)+1}} と b f ( i ) + 1 {\displaystyle b_{f(i)+1}} は計算定義 1 で定義されたもの。
q j ∉ { r 0 , r 1 , ...
形式的には、PDA は以下の6-タプルで定義される。
M = ( Q , Σ , Γ , δ , q 0 , F ) {\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}
ここで、
Q {\displaystyle \,Q} は状態の有限集合
Σ {\displaystyle \,\Sigma } は入力アルファベットの有限集合
Γ {\displaystyle \,\Gamma } はスタック上のアルファベットの有限集合
δ {\displaystyle \,\delta } : Q × Σ ε × Γ ε ⟶ P ( Q × Γ ε ) {\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma _{\epsilon }\longrightarrow P(Q\times \Gamma _{\epsilon })} は遷移関数
q 0 {\displaystyle q_{0}} は開始状態
F ⊂ Q {\displaystyle F\subset Q} は受容(受理)状態の集合
Γ ε = Γ ∪ { ε } {\displaystyle \Gamma _{\epsilon }=\Gamma \cup \{\epsilon \}}
Σ ε = Σ ∪ { ε } {\displaystyle \Sigma _{\epsilon }=\Sigma \cup \{\epsilon \}}