Закрытие Клини в нормальной форме Хомского

Question

Пусть n будет любым терминалом.

Рассмотрим следующее, предположительно правильное, представление клинской звезды над n:

N → n N | ε

(где ε - пустой терминал.)

Википедия говорит:

Каждая грамматика в нормальной форме Хомского не зависит от контекста, и, наоборот, каждая не зависящая от контекста грамматика может быть преобразована в эквивалентную грамматику в нормальной форме Хомского.

Я не вижу, как приведенная выше грамматика может быть преобразована в CNF.

• Разве грамматика не является контекстно-свободной?
• Есть ли способ представить его в CNF?

Answer 1

К счастью, об этом можно написать в CNF. Вот одна из таких грамматик:

S → ε | п | Не Доступно

N → n

A → n | Не Доступно

Поэтому язык не зависит от контекста.

Надеюсь это поможет!