プッシュダウン・オートマトン
言語 { 0 n 1 n | n ≥ 0 } {\displaystyle \{0^{n}1^{n}|n\geq 0\}} を認識するPDAの形式定義は以下の通りである。
M = ( Q , Σ , Γ , δ , q 1 , F ) {\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{1},\ F)}
Q = { q 1 , q 2 , q 3 , q 4 } {\displaystyle Q=\{q_{1},q_{2},q_{3},q_{4}\}}
Σ = { 0 , 1 } {\displaystyle \Sigma =\{0,1\}}
Γ = { 0 , $ } {\displaystyle \Gamma =\{0,\$\}}
F = { q 1 , q 4 } {\displaystyle F=\{q_{1},q_{4}\}}
δ ( q 1 , ε , ε ) = { ( q 2 , $ ) , ( q 1 , ε ) } {\displaystyle \delta (q_{1},\epsilon ,\epsilon )=\{(q_{2},\$),(q_{1},\epsilon )\}}