При n> = 0, является ли данная грамматика (a^na^na^n) контекстом свободной? Я пробовал использовать лемму накачки, и результат был, нет, это не контекст.Является ли следующая языковая контекстная свободная грамматика?
Для того, чтобы лекция о перекачке работала, вам нужно показать, что вы можете найти слово и «нагреть его», чтобы нарушить правила PL.
В этом случае у вас есть a^n a^n a^n и вы хотите разбить эти слова на слово uv^kw так, чтобы оно все еще было в указанной грамматике.
В этом случае он НЕ будет работать!
Чтобы убедиться в этом, мы должны думать о нескольких случаях:
1) и составляет по меньшей мере 1 (как v не может быть пустыми по определению PL), что делает V и W остальной части элементов а
2) и имеет в длину a^n, v имеет длину по меньшей мере^п и ш имеет длину a^n
3) ...
Представьте, что вы есть трафарет длины к и положить его при любом воображаемом положении a^na^n а^п так:
Если вы только добавить 1 п, полученное слово обыкновение быть больше в a^n a^n a^n, поэтому PL не удается. Язык a^n a^n a^n равен a^n b^n c^n, который является стандартным примером неудачной PL.
Sidenote: Если PL не подведет, вы не можете сделать вывод о том, что грамматика не имеет контекста. PL работает только в одном направлении.
Если вы можете доказать, что это не является контекстом с помощью леммы о перекачке, то это не контекст бесплатно. Если вы хотите, чтобы кто-то подтвердил ваше доказательство, вы должны включить доказательство в вопрос. Но stackoverflow не является подходящим местом, чтобы попросить людей проверить доказательства, поскольку это не имеет никакого отношения к программированию; вы можете попробовать http://cs.stackexchange.com/ – rici
ok man, что угодно! –