チョムスキー普通形に変換

Question

私はあなたの助けが必要です。

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

私はチョムスキー標準形（CNF）を適用する必要があります は、私はこれらの作品を持っています。私がすべき上記のルール適用するためには

：εproducions

を排除

1. は、単一の制作
2. を排除すぐに私は動けなく無用のシンボル

を削除します。その理由は、Aはnull可能なシンボルです（εはボディの一部です）。

もちろん、Aシンボルは削除できません。

誰でも最終的な解決策を手に入れることができますか？

Answer 1

Wikipediaの注釈として、ε生成の処理が異なるチョムスキー正規形の定義が2つあります。他の定義に続くCNF文法はそれに対応していませんが、文法は空文字列を生成します。

Answer 2

（Wikipediaのページで定義されている定義（1）を使用して）Chomskyの標準形式に変換するには、本質的に非契約の文法を見つける必要があります。開始記号Sと文法Gは、本質的に非再帰的な開始記号を使用して文法G、同等の文法G'を呼び出す

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

場合に限っnoncontractingされることである。明らかに

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

、NULL可能変数のセットG'はであり、A -> εはG'の生産であり、S -> Aはチェーンルールです。私はあなたが文法からε-ルールを取り除くためのアルゴリズムを与えられたと仮定します。

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

文法G''本質的noncontractingされ;そのアルゴリズムは次のように文法が生じるはずです残りのアルゴリズムを文法に適用して、Chomsky正規形の同等の文法を見つけることができます。