0

文法をチョムスキー標準形に翻訳する練習をしようとしています。私は通常の状況でこれを行う方法を理解していますが、今回は私が使用している文法は正しい再帰的です。（技術的には、文法は前の質問に対する答えなので、ガンマが間違っている可能性があります。）

εルールの代わりに固定シーケンスのルールを使用することでこれを実行できると思いますが、間違った方向に向かっていないことを確認したいと思います。例を使って説明する方が簡単です。

nが0より大きく3の倍数であるn'aを生成する文法の場合:(心配しないでください。これは私の実際の文法とはまったく異なります）

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

正しい翻訳は次のようになりますか？

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

1 に答える 1

1

文法は右再帰ですが、他の (非右再帰) 文法と同じようにチョムスキー標準形変換を実行できます。あなたの本に概説されているアルゴリズムに従ってください。おそらく次の 2 つのステップで構成されています。(2)新しい変数を含む長さ 2 の規則によって、len (w) > 2 であるすべての規則A -> wを変換します。

Aルールの場合、端子を導出するためのルールを作成し、たとえばK -> aとし、端子aのすべての出現箇所を置き換えます。

A -> AKKK

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

A    -> AA'
A'   -> KA''
A''  -> KK
于 2010-11-23T19:26:07.180 に答える