オートマトンまとめ

決定性プッシュダウンオートマトン … DPDA
非決定性プッシュダウンオートマトン … NPDA

最終状態受理方式と空スタック受理方式の２つがある

• NPDAでは２つの受理方式を相互に変換できる

• DPDAの場合，DPDAで受理する言語がプレフィックス性を持てば相互に変換できる．
• 空スタック受理方式のDPDAが受理する言語はプレフィックス性を持つ

• プレフィックス性を持たない言語Lを受理する最終状態受理方式DPDAは，つくれるかもしらん
• プレフィックス性を持たない言語Lを受理する空スタック受理方式DPDAは，つくれない

なんかもっとうまくまとまらんかなぁ