Нормальная форма Хомского - теория вычислений
Я хочу изменить грамматику на нормальную форму Хомского (CNF).
Это пример
S--> AB | ɛ
A--> aASb | a
B--> bS
Я пытаюсь решить это
S --> [A] [B]
[A] --> [aA] [Sb] | [a]
[aA] --> [a] A
[Sb] --> s [b]
[a] --> a
[b] --> b
Я не уверен насчет ответа. Кто-нибудь может сказать мне, если это правильно или неправильно?
3 ответа
Одна ошибка в том, что вы удалили S --> ɛ переход. Тебе это нужно (S --> ɛ специально разрешено в CNF, хотя AnyNonTerminalOtherThanS --> ɛ не является).
Тогда правило [A] --> [a], должно быть [A] --> a потому что если у вас есть только один элемент в RHS, он должен быть терминалом.
[aA] --> [a] A
[Sb] --> s [b]
Эти два кажутся опечатками, как A а также s не существует Вы, вероятно, имели в виду:
[aA] --> [a] [A]
[Sb] --> [S] [b]
Кроме того, то, что у вас есть, правильно.
Чтобы написать нормальную форму Хомского к приведенному выше вопросу.. Получите форму либо S->AB (или) S->aB
[аА] --> [а] [А] [Сб] --> [С] [б]
[нормальная форма Хомского][1]
Щелкните здесь, чтобы увидеть пример нормальной формы Хомского [1]: https://stackru.com/images/d771ede09ce60d601ad39ccff76b3473abd64087.jpg