正しい再帰文法をチョムスキーの通常の形に変換します

Question

私は文法をチョムスキーの通常の形に翻訳する演習をしようとしています。私は通常の状況でこれを行う方法を理解していますが、今回は私が働いている文法は正しい再帰です。 （技術的には、文法は前の質問に対する答えですので、私は間違ったガンマを持っているかもしれません。）

εルールの代わりに一連のルールを使用してこれを行うことができると思いますが、間違った方向に向かっていないことを確認したいと思います。例で説明する方が簡単です：

N 'Aを生成する文法の場合、nは0より大きく、3つの倍数：（心配しないでください、これは文法とはまったく異なります私の実際の演習）

S-> Aaaa
A-> Aaaa
A-> ε

正しい翻訳は次のとおりです。

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

あなたの文法は正しい再回復的ですが、他の（右の再帰的な）文法と同様に、チョムスキーの通常のフォーム変換を実行できます。本に概説されているアルゴリズムに従ってください。おそらく2つの手順で構成されています。（1）端子のすべての発生を置き換える a ルールによって a-> a, 、 どこ a ルールセットでは発生しません。 （2）すべてのルールを変換します a-> w, 、 どこ レン（w）> 2、新鮮な変数を含む長さ2のルールによる。

あなたのための a ルール、次に、ターミナルを導出するためのルールを構築し、たとえば k-> a, 、端子のすべての発生を交換します a:

A -> AKKK

次に、文法をCNFに入れます

A    -> AA'
A'   -> KA''
A''  -> KK