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

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

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

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

Ответ 1

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

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

Ответ 2

Для контекстного свободного языка один быстрый метод - просто посмотреть количество сравнений.
В примере см. 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} является контекстным, поскольку он имеет только одно сравнение (не регулярное)

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