Jak ustalić, czy język jest rekurencyjny czy rekursywnie przeliczalny?

Question

Muszę określić, czy język (na przykład L = {a^nb^mc^s | 0 < = n < = m < = s}) jest regularny, bezkontekstowy, rekursywny, rekurencyjnie wyliczalny lub żaden z nich .

Wiem, jak ustalić, czy dany język jest regularny (znaleźć DFA lub wyrażenie regularne, które działa), czy bezkontekstowy (znajdź gramatykę PDA lub gramatykę bezkontekstową, która działa); Wiem, że język rekursywny ma maszynę Turinga, która zawsze zatrzymuje się i że rekursywnie przeliczalny język ma maszynę Turinga, która nie może się zatrzymać.

Pytanie brzmi: czy istnieje szybkie kryterium do określenia, czy dany język jest rekursywny, czy rekursywnie przeliczalny, czy też nie? Na przykład, nie muszę budować PDA, aby zrozumieć, że język jest pozbawiony kontekstu, nie widzę go przez to, że wymaga jednego stosu; czy istnieje podobne szybkie podejście do problemu (który, mam nadzieję, oszczędza kłopotów z budową maszyny Turinga)?

Answer 1

Nie ma strukturalnego sposobu sprawdzenia, czy język jest rekursywny, czy rekurencyjnie przeliczalny. Jest naprawdę fajny dowód, który mówi, że dla każdego automatu zdolnego do rozpoznawania języków rekursywnych, istnieje co najmniej jeden język RE w R, który akceptuje także automat; jest to wariant argumentu przekłamania, którego używasz do pokazania istnienia nierozstrzygalnych problemów.

Głównym sposobem, w jaki dowodzisz językiem, jest RE, ale nie R jest dowodem, że język jest w RE (może definiując TM dla niego), a następnie zredukować znany problem z RE, ale nie R do tego problem. Na przykład, jeśli możesz pokazać, że dowolne wystąpienie problemu zatrzymania można rozwiązać, przekształcając go w instancję problemu, wiesz, że nie może on mieć rozwiązania rekursywnego i jeśli podążasz za tym z TM dla język, który znasz, że język jest w RE. Razem, masz język w RE, ale nie R.

Answer 2

Dla języka bez kontekstu jedną szybką metodą jest po prostu zobaczyć liczbę porównań.
W tym przykładzie patrz n<=m i m<=s. Są więc dwa porównania. Możesz więc go wyrzucić, po prostu mówiąc, że nie ma kontekstu. Jeśli istnieje pojedyncze porównanie, wówczas nazwij je językiem bez kontekstu.

To samo dotyczy standardowych języków. Nie powinno być związku między tymi dwiema zmiennymi, tzn. Nie może być żadnego porównania. Na przykład rozważ języki - 0^m+n 1^n 0^m. Ostrożnie zobacz, że dokonano tylko jednego porównania, które jest m+n = n+m (przesuwanie i trzaskanie symboli), więc jest wolne od kontekstu.
Teraz zobacz 0^n+m 1^n+m 0^m wyraźnie zobaczyć porównanie między 2 pierwszych i dwóch następnych.

Zajęło mi trochę czasu, aby to rozgryźć. Ale podejmowanie decyzji zajmie trochę czasu. Uwierz mi, że to naprawdę działa. Oto ostatni przykład zwykłego języka. a^n b^2m jest regularny (Patrz nie ma porównania między n oraz m) i {a^n b^m |n=2m} kontekst jest wolny, ponieważ ma tylko jedno porównanie (nie regularny)

Hope this helps