Как определить, является ли язык рекурсивным или рекурсивно перечислимым?

Question

Я должен определить, является ли язык (например, L = {a ^ nb ^ mc ^ s | 0 <= n <= m <= s}) регулярным, не зависящим от контекста, рекурсивным, рекурсивно перечислимым или нет их. </p>

Я знаю, как определить, является ли язык регулярным (найти DFA или регулярное выражение, которое работает) или контекстным (найти КПК или контекстную грамматику, которая работает); Я знаю, что у рекурсивного языка есть машина Тьюринга, которая всегда останавливается, и что у рекурсивно перечислимого языка есть машина Тьюринга, которая может не останавливаться.

Таким образом, возникает вопрос: существуют ли быстрые критерии для определения того, является ли язык рекурсивным или рекурсивно перечислимым, или нет? Например, мне не нужно создавать КПК, чтобы понять, что язык не зависит от контекста, я не вижу этого в том, что для него требуется один стек; Есть ли такой же быстрый подход к проблеме (который, мы надеемся, избавит от необходимости строить машину Тьюринга)?

Answer 1

Для контекстно-свободного языка один быстрый метод - просто посмотреть количество сравнений.
В примере смотрите n<=m и m<=s. Таким образом, есть два сравнения. Таким образом, вы можете взять это, просто сказав, что это не контекстно-свободный Если используется только одно сравнение, тогда назовите его как язык без контекста.

То же самое и с обычными языками . Не должно быть никакой связи между этими двумя переменными, я имею в виду, что не должно быть никакого вида сравнения. Для примера рассмотрим языки - 0^m+n 1^n 0^m. Тщательно проследите, чтобы было выполнено только одно сравнение: m+n = n+m (нажатие и извлечение символов). Таким образом, оно не зависит от контекста.
Теперь смотрите 0^n+m 1^n+m 0^m, ясно видите сравнение между первыми 2 и следующими двумя.

Мне понадобилось время, чтобы понять это. Но это займет некоторое, чтобы принять решения. Поверьте мне, это действительно работает. Вот последний пример для обычного языка. a^n b^2m является регулярным (см. Нет сравнения между n и m), а {a^n b^m |n=2m} является контекстно-свободным, поскольку имеет только одно сравнение (не регулярное)

Надеюсь, это поможет

Answer 2

Нет структурного способа проверить, является ли язык рекурсивным или рекурсивно перечислимым.На самом деле есть действительно классное доказательство, которое говорит, что для любого автомата, способного распознавать рекурсивные языки, существует по крайней мере один язык RE, не принадлежащий R, который автомат также принимает;это вариант аргумента диагонализации, который вы используете, чтобы показать существование неразрешимых проблем.

Основной способ, которым вы доказываете, что язык находится в RE, а не R - это доказывать, что язык находится в RE (возможно, путем определенияТМ для него), а затем уменьшить известную проблему в RE, но не R к этой проблеме.Например, если вы можете показать, что любой экземпляр проблемы остановки можно решить, превратив его в экземпляр вашей проблемы, вы знаете, что у него не может быть рекурсивного решения, и если вы добьетесь этого с TM дляязык вы знаете, что язык в RE.Вместе у вас есть язык в RE, но нет R.