Преобразование грамматики в нормальную форму Хомского?

Преобразовать грамматику ниже в нормальную форму Хомского . Приведите все промежуточные шаги.

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 , которые не существовали. И это был ответ, который я придумал: мне нужно что-то делать дальше, или я сделал что-то не так?

10
задан Brian Tompsett - 汤莱恩 26 May 2015 в 08:08
поделиться