pushdown automaton

pushdown automatonは、計算理論において有限オートマトンにスタックというメモリ構造を加えたモデルです。これにより、単純な有限オートマトンでは不可能な、括弧の対応関係のような入れ子構造や、回数のカウントが必要な言語を認識できるようになります。

計算能力の拡張と文脈自由言語

このモデルの最大の特徴は、後入れ先出し（LIFO）形式のスタックを利用して情報を一時的に保存できる点にあります。これにより、pushdown automatonは文脈自由言語を完全に認識することができ、これはプログラミング言語の構文解析（パース）において極めて重要な役割を果たします。例えば、数式内の括弧が正しく閉じられているかを確認する場合、開き括弧をスタックに積み（push）、閉じ括弧が現れた際にそれを取り出す（pop）ことで整合性を判定します。

決定性と非決定性の違い

pushdown automatonには、決定性（DPDA）と非決定性（NPDA）の2種類が存在します。有限オートマトンの場合は決定性と非決定性が同等の能力を持ちますが、プッシュダウン・オートマトンの場合は異なります。非決定性モデルの方がより広い範囲の言語を認識でき、特に多くの文脈自由言語を扱うには非決定的な動作が必要となります。実用的なコンパイラのパーサでは、効率化のために決定性プッシュダウン・オートマトンのサブセットであるLLパーサやLRパーサなどが利用されています。