PDAと文脈自由文法

文法 G がコンテキストフリーの場合、コンテキストフリーの文法 G によって生成される言語を受け入れる同等の非決定性PDAを構築できます。文法 G のパーサーを構築できます。

また、 P がプッシュダウンオートマトンである場合、同等の文脈自由文法Gを構築できます。

次の2つのトピックでは、PDAからCFGへ、またはその逆への変換方法について説明します。

特定のCFGに対応するPDAを見つけるアルゴリズム

入力-A CFG、G =（V、T、P、S）

出力-等価PDA、P =（Q、∑、S、δ、q〜0〜、I、F）

ステップ5 *- *A→aX の形式の各制作物に対して、aは終端で、 A、X は終端と非終端の組み合わせであり、遷移*δ（q、a、A）*を行います。

次のCFGからPDAを構築します。

プロダクションがあります-

*S→XS | ε、A→aXb | Ab | ab*

同等のPDAを、

P =（\ {q}、\ {a、b}、\ {a、b、X、S}、δ、q、S）

ここで、δ−

δ（q、ε、S）= \ {（q、XS）、（q、ε）}

δ（q、ε、X）= \ {（q、aXb）、（q、Xb）、（q、ab）}

δ（q、a、a）= \ {（q、ε）}

δ（q、1、1）= \ {（q、ε）}

入力-A CFG、G =（V、T、P、S）

出力-文法Gの非終端が\ {X〜wx〜|になるような等価PDA、P =（Q、∑、S、δ、q〜0〜、I、F） w、x∈Q}であり、開始状態はA〜q0、F〜になります。

ステップ1 *-δ（w、a、ε）に（y、m）および（z、b、m）が含まれる場合、w、x、y、z∈Q、m∈S、およびa、b∈∑ごとに（x、ε）を含む場合、生成規則X〜wx〜→a X〜yz〜bを文法Gに追加します。