Преобразовать грамматику ниже в нормальную форму Хомского . Приведите все промежуточные шаги.
S -> AB | aB
A -> aab|lambda
B -> bbA
Хорошо, первое, что я сделал, это добавил новую начальную переменную S0
, так что теперь у меня есть
S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA
, затем я удалил все лямбда-правила:
S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb
Затем я проверил наличие S -> правила типа S
и A-> B
, которые не существовали. И это был ответ, который я придумал: мне нужно что-то делать дальше, или я сделал что-то не так?