context-free-grammar - このチョムスキー形式の解き方

Question

S → aSab | ABB | BB

A → baab | BABB | AaA

B → bAaBa | bb | b

私はそれを解決し始めましたが、追いつくために新しいルールを追加し続けているようです。誰かがこれを行う方法を説明してもらえますか.

Answer 1

これは、チョムスキー標準形での結果の文法です。
非終端記号のセット、終端記号のセット、規則、および開始記号の 4 つのタプルによってそれぞれ定義されます。

G = ({S,A,B,<Sab>,<ab>,<BB>,<aab>,<ABB>,<aA>,<AaBa>,<aBa>,<Ba>,a',b '},{a,b},R,S)

R =
S → a'<サブ> | A<BB> | BB
A → b'<aab> | B<ABB> | A<aA>
B → b'<AaBa> | b'b' | b
<Sab> → S<ab>
<ab> → a'b'
<BB> → BB
<aab> → a'<ab>
<ABB> → A<BB>
<aA> → a'A
<AaBa> → A<aBa>
<aBa> → a'<Ba>
<Ba> → Ba'a' →
a
b' → b

必要に応じて、山括弧 <> 内の非終端文字の名前を 1 文字の大文字記号に自由に変更してください (1 つの非終端文字を意味します)。これはより適切だと思います。