プッシュダウン・オートマトン
任意のPDA、 M = ( Q , Σ , Γ , δ , q 0 , F ) {\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)} について、計算経路の順序は (n+1)-タプル ( q 0 , q 1 , . . . . , q n ) {\displaystyle (q_{0},\,q_{1},....,\,q_{n})} で表され(ここで q i ∈ Q , n ≥ {\displaystyle q_{i}\in Q,n\geq } 0 )、以下の条件が成り立つ。
i = 0 , 1 , 2 , ... , n − 1 {\displaystyle i=0,1,2,\dots ,n-1} について、 ( q i + 1 , b i + 1 ) ∈ δ ( q i , w i + 1 , a i + 1 ) {\displaystyle \ \ (q_{i+1},b_{i+1})\in \delta (q_{i},w_{i+1},a_{i+1})} ここで w i + 1 ∈ Σ ε , a i + 1 , b i + 1 ∈ Γ ε {\displaystyle w_{i+1}\in \Sigma _{\epsilon },\ a_{i+1},\ b_{i+1}\in \Gamma _{\epsilon }}
∃ s 0 , s 1 , s 2 , s 3 , ...
a i + 1 {\displaystyle a_{i+1}} も b i + 1 {\displaystyle b_{i+1}} も ε {\displaystyle \epsilon } の可能性もある。
a i + 1 ≠ ε {\displaystyle a_{i+1}\neq \epsilon } かつ b i + 1 ≠ ε {\displaystyle b_{i+1}\neq \epsilon } なら、PDA はスタックから記号を読み取り、それを別の記号に置換する。
a i + 1 ≠ ε {\displaystyle a_{i+1}\neq \epsilon } かつ b i + 1 = ε {\displaystyle b_{i+1}=\epsilon } なら、PDA はスタックから記号を読み取り、単にそれを削除する。
a i + 1 = ε {\displaystyle a_{i+1}=\epsilon } かつ b i + 1 ≠ ε {\displaystyle b_{i+1}\neq \epsilon } なら、PDA は単に記号をスタックに追加する。
a i + 1 = ε {\displaystyle a_{i+1}=\epsilon } かつ b i + 1 = ε {\displaystyle b_{i+1}=\epsilon } なら、PDA はスタックを更新しない。
n = 0 {\displaystyle n=0} の場合、計算経路はシングルトンとなる ( q 0 ) {\displaystyle (q_{0})} 。