以下の文法をチョムスキー標準形に変換します。すべての中間ステップを実行します。
S -> AB | aB
A -> aab|lambda
B -> bbA
さて、私が最初にしたことは、新しい開始変数を追加することでしたS0
だから今私は持っています
S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA
次に、すべてのラムダルールを削除しました。
S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb
次に、存在しないルールをチェックしS->Sて入力しました。A->Bそしてそれが私が思いついた答えでした、私はさらに何かをする必要がありますか、それとも私は何か間違ったことをしましたか？
ウィキペディアによると：
コンピュータサイエンスでは、すべての生成規則が次の形式である場合、文脈自由文法はチョムスキー標準形であると言われます。
- A- > BC、または
- A- >α、または
- S- >ε
ここで、A、B、Cは非終端記号、αは終端記号、Sは開始記号、εは空の文字列です。また、BもCも開始記号であってはなりません。
作業を継続する：
S0 -> S S -> AB | aB | B A -> aab B -> bbA | bb
異なる選択肢を示すために使用する代わりに|、ルールを複数のルールに分割します。
S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb
新しいルールY -> aを作成しますZ -> b。すぐに必要になるためです。
S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b
S -> aBは端末であるS -> BCため、形式ではありません。aだからに変更aしYます：
S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b
B -> bbルールについても同じようにします。
S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> ZZ Y -> a Z -> b
の場合A -> aab、作成しますC -> YY。の場合B -> bbA、作成D -> ZZ：
S0 -> S S -> AB S -> YB S -> B A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
の場合、右側S -> Bで発生する1つのルールを複製し、ルールをインライン化します。S
S0 -> B S0 -> S S -> AB S -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
ルールS0 -> Bを処理S0 -> Sし、他のルールの右側を左側に結合します。また、孤立したルールを削除します（RHSでLHSシンボルが使用されることはありません）。
S0 -> DA S0 -> ZZ S0 -> AB S0 -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
これで完了です。ふぅ！
あまり多くの理論と証明（ウィキペディアでこれを見ることができます）に入ることなく、文脈自由文法をチョムスキー標準形に変換するときにしなければならないことがいくつかあります。通常、4つの正規形変換を実行する必要があります。まず、直接または間接的に空の文字列（lambda / epsilon）を生成できるすべての変数を特定する必要があります-（ラムダフリー形式）。次に、ユニットプロダクションを削除する必要があります-（ユニットフリーフォーム）。第三に、あなたは生きている/役に立つ（有用性）すべての変数を見つける必要があります。4つ目は、到達可能なすべてのシンボル（Reachable）を見つける必要があります。各ステップで、新しい文法がある場合とない場合があります。だからあなたの問題のためにこれは私が思いついたものです...
文脈自由文法
G(Variables = { A B S }
Start = S
Alphabet = { a b lamda}
Production Rules = {
S -> | AB | aB |
A -> | aab | lamda |
B -> | bbA | } )
ラムダ/イプシロンを削除します
ERRASABLE(G) = { A }
G(Variables = { A S B }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | B |
B -> | bbA | bb | } )
ユニット製品を削除します
UNIT(A) { A }
UNIT(B) { B }
UNIT(S) { B S }
G (Variables = { A B S }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | bb | bbA |
A -> | aab |
B -> | bbA | bb | })
ライブシンボルを決定する
LIVE(G) = { b A B S a }
G(Variables = { A B S }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | bb | bbA |
A -> | aab |
B -> | bbA | bb | })
到達不能なものを削除します
REACHABLE (G) = { b A B S a }
G(Variables = { A B S }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | bb | bbA |
A -> | aab |
B -> | bbA | bb | })
すべての混合文字列を非終端記号で置き換えます
G( Variables = { A S B R I }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | RB | II | IIA |
A -> | RRI |
B -> | IIA | II |
R -> | a |
I -> | b | })
チョムスキー標準形
G( Variables = { V A B S R L I Z }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | RB | II | IV |
A -> | RL |
B -> | IZ | II |
R -> | a |
I -> | b |
L -> | RI |
Z -> | IA |
V -> | IA | })
別の答え：文法は有限数の文字列、つまり6つしか生成できません。
S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb.
これで、これを手作業でチョムスキー標準形に凝縮することができます。
代入することで、生成されたすべての文字列のセットを見つけることができます。あなたの最初のルール：
S -> AB | aB.
A -> aab | lambda.
B -> bbA.
S最初にルールを分割します。
S -> AB.
S -> aB.
次に、AとBが展開するものに置き換えます。
S -> AB
-> (aab | lambda) bbA
-> (aab | lambda) bb (aab | lambda).
S -> aB
-> abbA
-> abb (aab | lambda).
これらをもう一度展開して、以下を取得します。
S -> aabbbaab.
S -> aabbb.
S -> bbaab.
S -> bb.
S -> abbaab.
S -> abb.
この有限集合をチョムスキー標準形に変更するには、インテリジェントな因数分解を行わずにブルートフォースで行うだけで十分です。まず、2つのターミナルルールを紹介します。
X -> a.
Y -> b.
ここで、各文字列について、最初の文字を終端変数で消費し、残りの文字を新しい変数で消費します。たとえば、次のようになります。
S -> aabbb. (initial rule, not in Chomsky Normal Form)
S -> XC, where X->a and C->abbb.
C -> XD, where X->a and D->bbb.
D -> YE, where Y->b and E->bb.
E -> YY, where Y->b and Y->b.
6つの文字列すべてに対してこのプロセスを実行し、多くの新しい中間変数を生成します。