Почему это не контекстно-свободная грамматика?

Question

Я смутно напоминаю, что {a ^ nb ^ nc ^ n is, n> = 0} не является контекстно-свободным.

Но не является ли следующая допустимая контекстно-свободная грамматика, которая фиксирует вышеуказанное

S -> abcS S -> null

Цитата из Википедии:

"В теории формального языка не зависящая от контекста грамматика (CFG) - это формальная грамматика, в которой каждое производственное правило имеет форму V → w, где V - один нетерминальный символ, а w - строка терминалов и /или нетерминалы (w может быть пустым). "

Answer 1

S -> abcS производит что-то подобное (abc) ^ n не a ^ nb ^ nc ^ n

Answer 2

На тот случай, если вам интересно, почему это не контекстная грамматика, вот краткое объяснение:

Не зависящая от контекста грамматика - это грамматика, которая может быть распознана автоматом, который является конечнымавтомат состояний с добавлением стека.

Примером CFG является ^ nb ^ n.Если вы думаете об этом, мы можем вставить токен в наш стек для каждого «a», который мы видим, и вытолкнуть токен из стека для каждого «b», который мы видим.Мы потерпим неудачу в любой момент, если мы - нажмем токен после выталкивания (a 'b', сопровождаемый 'a') - закончим обработку строки, но у нас все еще есть токены в стеке (больше 'a's, чем' b) - попытаемсявытолкнуть пустой стек (больше «b» чем «a»)

Если вы подумаете о том, как распознать ^ nb ^ nc ^ n с автоматом, вы, вероятно, поймете, что это невозможно после некоторой игры вокруг.

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

Answer 3

Для n = 2 производство не должно быть: aabbcc? Но разве ваш пример грамматики не даст abcabc?

Answer 4

Вы написали производственное правило, которое генерирует abc ^ n, а не ^ nb ^ nc ^ n.