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

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

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

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


recursion computer-science turing-machines context-free-grammar
person Jacob    schedule 16.02.2011    source источник

Ответы (2)


arrow_upward
5
arrow_downward

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

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

person templatetypedef    schedule 16.02.2011
comment
Это определенно не тот ответ, на который я надеялся :( хотя он проясняет некоторые сомнения, которые у меня были, так что спасибо! Итак, если бы вам нужно было решить пример, который я написал в начале, как бы вы поступили (зная, что это не контекст -бесплатно)? - person Jacob; 16.02.2011
comment
@Jacob- Вы уверены, что это не контекстно-свободно? - person templatetypedef; 16.02.2011
comment
Почти уверен, да. Лемма о накачке должна исключить это, также я не могу найти грамматику, которая бы работала. - person Jacob; 16.02.2011
comment
@Jacob- Хорошо, круто. Не существует жесткого правила о том, как проверить, находится ли что-то в R или RE — R, но помните, что R — очень мощный класс языков. Большинство задач, связанных со счетом, находятся в R, и хорошее эмпирическое правило состоит в том, что если вы можете придумать простую компьютерную программу для ее решения, то она и в R. В этом случае не могли бы вы написать программу, которая проверяла бы правильное строковое условие? верно? - person templatetypedef; 16.02.2011
comment
Да, я думаю, это было бы довольно просто... так что вы думаете, что было бы неплохо сказать, что это на R, верно? - person Jacob; 17.02.2011
comment
@ Джейкоб, ага. Я бы предложил формализовать это, разработав законную TM (или TM с несколькими лентами), чтобы доказать, что вы правы. - person templatetypedef; 17.02.2011
comment
Ок, понял! Большое спасибо за ваше время и помощь :) - person Jacob; 17.02.2011

arrow_upward
5
arrow_downward

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

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

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

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

person Saurabh Srivastava    schedule 30.01.2012
comment
@ saurabh srivastav что бы вы сказали о L={a^n b^m| n,m›=1}, это КЛЛ? - person aparajita rai; 28.01.2013
comment
@aparajitarai Я бы сказал, что L - это обычный язык, поскольку вас не волнует соотношение между количеством букв a и количеством b, вы просто говорите, что каждая строка в языке должна начинаться с некоторого не- пустой префикс a размера n (однако не определено, каким должно быть n), за которым следует непустая последовательность b (где верхняя граница m по длине снова не ограничена), поэтому вы можете фактически построить регулярное выражение для этого языка. Пожалуйста, поправьте меня, если я ошибаюсь. Я просто прохожу курс теоретической информатики в своем колледже. - person jcxz; 04.02.2014