computer-science - 左再帰規則のない文法

Question

G を文法とする:

S --> A | B

A --> aaB | Aab | Aba

B --> bB | Bb | aba

左再帰規則を含まず、G と等価な新しい文法 G' を構築します。

これが私が思いついた答えですが、それを教授に持って行ったところ、彼はそれは間違っていると忠告しました。後で成績のために提出する必要があるため、彼はそれを修正する方法を教えてくれませんでした. すべての助けに感謝します。私はこれについて非常に混乱しており、すべての洞察に大いに感謝しています

GL: S0→ S | λ
S→ ABC | AB
A→ aA | a
B→ bB | A
C→ cC

Answer 1

これはどうですか：

S -> A | B
A -> aaC
C -> bC | D
D -> abaE
E -> bE | F
F -> λ | ab | ba
B -> bB | G
G -> aba | H
H -> b | bH