PDAと文脈自由文法

文法の場合 G は文脈自由であるため、文脈自由文法によって生成された言語を受け入れる同等の非決定論的PDAを構築できます。 G。文法用のパーサーを作成できますG。

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

L(G) = L(P)

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

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

Input − A CFG、G =（V、T、P、S）

Output−同等のPDA、P =（Q、∑、S、δ、q ₀、I、F）

Step 1 −CFGの生成をGNFに変換します。

Step 2 −PDAの状態は1つだけです{q}。

Step 3 − CFGの開始記号は、PDAの開始記号になります。

Step 4 − CFGのすべての非終端記号はPDAのスタック記号になり、CFGのすべての終端記号はPDAの入力記号になります。

Step 5 −フォーム内の各プロダクションについて A → aX ここで、aは端末であり、 A, X 終端記号と非終端記号の組み合わせであり、遷移を行います δ (q, a, A)。

次のCFGからPDAを作成します。

G = ({S, X}, {a, b}, P, S)

ここで、プロダクションは-

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、ε）}

Input − A CFG、G =（V、T、P、S）

Output−同等のPDA、P =（Q、∑、S、δ、q ₀、I、F）で、文法Gの_非終端記号は{X _wx | w、_x∈Q }であり、開始状態はA _{q0、Fになり}ます。

Step 1−すべてのw、x、y、z∈Q、m∈Sおよびa、b∈∑について、δ（w、a、ε）に（y、m）が含まれ、（z、b、m）に（x、 ε）、生産を追加ルールX _WX →A X _YZ B文法G.で

Step 2-すべてのW、X、Y、Z∈Qについて、Xプロダクションルールを追加_WX →X _WY X _YX文法Gに

Step 3_{−w∈Qの場合}、文法Gに生成規則_Xww →εを追加します。