Является ли язык A = {0 ^ n 1 ^ n 0 ^ n} контекстно-бесплатным

Question

Я просто размышлял о разных языках (так как я готовлюсь к выпускным экзаменам), и я не могу придумать действительных автоматов, чтобы работать с языком A = {0 ^ n 1 ^ n 0 ^ n | n> = 0}. Это не контекстно-зависимый язык, я прав?

Answer 1

Я верю, что вы есть. Это выглядит очень похоже на язык L = {a ^ i b ^ i c ^ i | i> 0} , которую в статье Википедии о использует лемма прокачки в качестве примера того, как доказать, что язык не является контекстно-свободным.

Answer 2

Подумайте только о части {0 ^ n 1 ^ n} на секунду. Замените 0 на ( и 1 на ), и вы получите язык простых вложенных скобок, который является мертвой раздачей, что язык не является регулярным.

Добавление последнего 0 ^ n делает его контекстно-зависимым (т.е. не контекстно-свободным). Имейте в виду, что CFG может быть определен конечным компьютером с единственным стеком в качестве единственной структуры данных. Увидение 0 приведет к тому, что символ будет помещен в стек, а вид 1 выскочит из стека. Это гарантирует, что будет 0, а не 1, но тогда нет способа сопоставить больше 0.