Я просто размышлял о разных языках (как я рассматриваю для выпускных экзаменов), и я не могу думать о допустимых автоматах для толкания для обработки языка A = {0^n 1^n 0^n | n> = 0}. Это не контекстно-свободный язык, я прав?Является ли язык A = {0^n 1^n 0^n} контекстом свободным?
Я считаю, что вы находитесь. Он очень похож на язык L = {a^i b^i c^i | i> 0}, который в статье Википедии the pumping lemma использует в качестве примера того, как доказать, что язык не является контекстным.
К оригинальному плакату я предлагаю попытаться выполнить те же действия, что и выше, с интересующим вас языком. –
что язык не справляется с леммой о пересылке для CFLS – jfisk
Подумайте только о части {0^n 1^n} на секунду. Замените 0 на ( и 1 с ), и у вас есть язык простых вложенных круглых скобок, что является мертвой отдачей, что язык не является регулярным.
Добавление окончательного 0^n делает его контекстно-зависимым (т. Е. Неконфликтным). Имейте в виду, что CFG можно решить с помощью компьютера с конечным состоянием с единственным стеком в качестве единственной структуры данных. Если увидеть 0, это приведет к тому, что персонаж будет помещен в стек, и увидит, как 1 появится из стека. Это гарантирует, что количество 0 равно 1, но нет возможности сопоставить еще 0's.
Возможный дубликат http://stackoverflow.com/questions/2617675/theory-of-comput-using-the-pumping-lemma-for-context-free-languages –
@Andrew Это отдельные языки :) – Tony
@ Andrew: plus, «regular» и «context-free» - совершенно разные * классы * языков – SamB