Klasyfikacja języków (rekurencyjne czy rek. policzalne?)

[lunex]

Sklasyfikuj (czy są rekurencyjne? czy są rekurencyjnie przeliczalne?) następujące języki:
K1= { <A>, A jest niedeterministycznym automatem skończonym i L(A) jest niepusty }
K2= { <G>, G jest gramatyką bezkontekstową i L(G) jest niepusty }
K3= { <M>, M jest maszyną Turinga i L(M) jest niepusty }
Odpowiedź uzasadnij.

Moim zdaniem:
K1 - rekurencyjny
K2 - rekurencyjnie policzalny
K3 - nie wiadomo/rekurencyjnie policzalny

Ale uzasadnić za bardzo nie umiem ;/ Byłby ktoś w stanie mi to wytłumaczyć i mógłby to zrobić?

[boo007]

K1 - rekurencyjny. Istnieje algorytm rozstrzygający, czy automat należy do zbioru, czy nie. Wystarczy sprawdzić, czy istnieje ścieżka ze stanu startowego do dowolnego ze stanów akceptujących (na przykład przeszukiwanie grafu w głąb).
K2 - rekurencyjny. Istnieje algorytm sprawdzający, czy język generowany przez gramatykę bezkontekstową jest pusty: Twierdzenie 2.4. z

Kod: Zaznacz cały

http://www.google.com/url?sa=t&source=web&cd=6&ved=0CEQQFjAF&url=http%3A%2F%2Fwww.logic.amu.edu.pl%2Fimages%2Fa%2Fa0%2FS2L.pdf&rct=j&q=gramatyka%20bezkontekstowa%20czy%20j%C4%99zyk%20jest%20niepusty&ei=NA3-TaDXJMqi-gba8qznAw&usg=AFQjCNFOK5nC4H0Tb_5QnqMk286mVQpCPQ&sig2=78XEoYFIVsL2yyXVyU8GFg&cad=rja

.
K3 - rekurencyjnie przeliczalny. Rozważmy program:

Kod: Zaznacz cały

wczytaj M
   for(int j=0; ; j++)
     for(int i=0; i< j; i++)
        uruchom M(i) na j sekund
        jeśli M(i) się zatrzymał return tak

Łatwo uzasadnić dlaczego program się zatrzymuje wtedy i tylko wtedy, jeśli istnieje liczba dla której M się zatrzymuje.
Chyba nie jest rekurencyjny, ale nie potrafię tego udowodnić w tej chwili.

[lunex]

ok, ogromne dzięki.

i żeby nie robić nowego tematu czy potrafiłbyś rozwiązać jeszcze taki problem:

Czy język:
K4= { (<A>,<G>), gdzie A jest niedeterministycznym automatem skończonym, G jest gramatyką bezkontekstową i L(A) =L(G) }
jest rekurencyjny? Podaj dowód uzasadniający swoją opinię.

[boo007]

K4 - nie wiem, dopełnienie jest rekurencyjnie przeliczalne (sprawdzamy po kolei wszystkie słowa dopóki nie natrafimy na różne). Znam algorytm sprawdzający (dla danych G i A), czy \(\displaystyle{ L(G) \subseteq L(A)}\), ale nie wiem czy istnieje algorytm sprawdzający czy \(\displaystyle{ L(A) \subseteq L(G)}\).

[Zordon]

Nie jest rekurencyjny. Problem: dana gramatyka \(\displaystyle{ G}\), stwierdzić czy generuje wszystkie słowa jest nierekurencyjny. Dowód opiera się na tym, że automatem niedeterministycznym ze stosem potrafię wykryć niepoprawną historię obliczeń maszyny Turinga. Można to chyba znaleźć na angielskiej wiki.