Существует ли не зависящий от контекста нерегулярный язык

13

Я знаю, что существуют нерегулярные языки, поэтому является регулярным, но все примеры, которые я могу найти, являются контекстно-зависимыми, но не контекстно-свободными.L

Если нет ни одного, как вы это докажете?

Саймон С
источник
1
Можно ответить с помощью тех же методов, что и cs.stackexchange.com/questions/1549
sdcvvc
2
Подсказка: все языки, содержащие алфавит, имеют очень простое замыкание Клини.
Рафаэль

Ответы:

20

зависит от контекста, но не является регулярным (классический пример). Так что L = { a n b nn Lзнак равно{aNбN|NN} .L'знак равно{aNбN|NN}{a,б}

регулярно.L'*знак равно{a,б}*

Жиль "ТАК - прекрати быть злым"
источник
2
Грубая сила, но действительная.
Рафаэль
, на самом деле ...L'знак равноL
vonbrand