Действительно ли язык = {0^n 1^n 0^n} свободный контекст?
Я просто помещал некоторую мысль в различные языки (поскольку я рассматриваю для итоговых экзаменов, подходящих), и я не могу думать о допустимых автоматах с магазинной памятью для обработки языка = {0^n 1^n 0^n | n> = 0}. Это не контекстно-свободный язык, я корректен?
2 ответа
Я верю, что да. Он очень похож на язык L = {a ^ i b ^ i c ^ i | i> 0} , который в статье Википедии о лемме о перекачке используется в качестве примера того, как доказать, что язык не является контекстно-независимым.
Подумайте только о части {0 ^ n 1 ^ n} на секунду. Замените 0 на ( и 1 на ) , и вы получите язык простых вложенных круглых скобок, что совершенно бесполезно. прочь, что язык не является регулярным.
Добавление последнего 0 ^ n делает его контекстно-зависимым (т. Е. Не зависимым от контекста). Имейте в виду, что CFG может быть определен конечным компьютером с одним стеком в качестве единственной структуры данных. Увидев 0, персонаж будет помещен в стек, а если увидеть 1, то он выскочит из стека. Это гарантирует, что нулей будет столько же, сколько единиц, но нет никакого способа сопоставить больше 0.