Нормальная форма Хомского - теория вычислений

Question

Я хочу изменить грамматику на нормальную форму Хомского (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

Я не уверен насчет ответа.Кто-нибудь может сказать мне, правильно это или неправильно?

Answer 1

Одна ошибка в том, что вы удалили переход S --> ɛ. Вам это нужно (S --> ɛ специально разрешено в CNF, хотя AnyNonTerminalOtherThanS --> ɛ нет).

Тогда правило [A] --> [a] должно быть [A] --> a, потому что если у вас есть только один элемент в RHS, он должен быть терминалом.

[aA] --> [a] A
[Sb] --> s [b]

Эти два кажутся опечатками, поскольку A и s не существует. Вы, вероятно, имели в виду:

[aA] --> [a] [A]
[Sb] --> [S] [b]

Кроме того, то, что у вас есть, правильно.