Для n> = 0 является ли данная грамматика (a ^ na ^ na ^ n) контекстной? Я пробовал использовать лемму о перекачке, и результат был, нет, это не контекстно-зависимый.
Является ли следующая языковая грамматика свободной от контекста?
comment
Если вы можете доказать, что это не контекстно-свободная лемма, то это не контекстно-свободная лемма. Если вы хотите, чтобы кто-то проверил ваше доказательство, вы должны указать его в вопросе. Но stackoverflow - не подходящее место, чтобы просить людей проверить доказательства, поскольку это не имеет ничего общего с программированием; вы можете попробовать cs.stackexchange.com
- person rici schedule 01.04.2015
Ответы (1)
Чтобы лемма о прокачке работала, вам нужно показать, что вы можете найти слово и «накачать его», чтобы нарушить правила PL.
В этом случае у вас есть a^n a^n a^n, и вы хотите разбить эти слова на слово uv ^ kw, чтобы оно все еще находилось в указанной грамматике.
В этом случае работать НЕ будет!
Чтобы убедиться в этом, мы должны подумать о нескольких случаях:
1) u не меньше 1 (поскольку v не может быть пустым по определению PL), поэтому v и w остаются
2) u имеет длину a^n, v имеет длину не менее a ^ n, а w имеет длину a^n
3) ...
Представьте, что у вас есть шаблон длины k и поместите его под каждую вообразимую позицию a ^ n a ^ n a ^ n следующим образом:
Если вы добавите только 1 n, результирующее слово больше не будет в a^n a^n a^n, поэтому PL завершится ошибкой. Язык a^n a^n a^n равен a^n b^n c^n, что является стандартным примером неудачного PL.
Примечание: если PL НЕ терпит неудачу, вы не можете сделать вывод, что грамматика контекстно-свободна. ЛП работает только в одном направлении.
person
hamena314
schedule
05.05.2015
