parsing - チョムスキー標準形への変換

Question

あなたの助けが必要です。私はこれらの作品を持っています：

1) A--> aAb
2) A--> bAa
3) A--> ε

チョムスキー正規形 (CNF) を適用する必要があります。

上記のルールを適用するには、次のことを行う必要があります。

すぐに行き詰まります。その理由は、A がヌル可能シンボルであるためです (ε はその本体の一部です)。

もちろん、A 記号を削除することはできません。

誰かが最終的な解決策を得るのを手伝ってくれますか?

score 2 · Accepted Answer

ウィキペディアが指摘しているように、チョムスキー標準形には2つの定義があり、ε生成の処理が異なります。これらが許可されているものを選択する必要があります。そうしないと、同等の文法が得られません。文法は空の文字列を生成しますが、他の定義に従うCNF文法はそれを実行できません。

score 2 · Accepted Answer

(ウィキペディアのページで提供されている定義 (1) を使用して) チョムスキー標準形への変換を開始するには、同等の本質的に非縮約文法を見つける必要があります。G開始記号を含む文法Sは、基本的に非縮約です。

1. S is not a recursive variable
2. G has no ε-rules other than S -> ε if ε ∈ L(G)

grammar を呼び出すと、再帰的でない開始記号を持つG同等の文法は次のようになります。G'

G' : S -> A
     A -> aAb | bAa | ε

明らかに、のヌル可能変数のセットはですG'。はで生成され、{S,A}はチェーンルールです。文法から ε 規則を削除するためのアルゴリズムが与えられたと仮定します。そのアルゴリズムは、次のような文法を生成する必要があります。A -> εG'S -> A

G'' : S -> A | ε
      A -> aAb | bAa | ab | ba

文法G''は本質的に非収縮です。残りのアルゴリズムを文法に適用して、チョムスキー標準形で同等の文法を見つけることができます。

2 に答える 2