Построение линейно-линейной грамматики

Question

Мне нужна помощь для построения линейно-линейной грамматики для языка {w ∈ {a, b} * | w не заканчивается на aa}.

Я построил правильную грамматику для языка {w ∈ {a, b} * | w не заканчивается на aa}, как показано ниже

S -> aA | bB | ε

A -> aC | bB | ε

B -> aA | bB | ε

C -> aC | bB

Как я могу построить правую линейную грамматику для того же самого?

Answer 1

Ваша грамматика уже прямо-линейная, так как:

1. Для каждого правила, есть только один нетерминал на правой стороне
2. В нетерминалах появляются только в конце