Strona 1 z 1
Klasyfikacja języków (rekurencyjne czy rek. policzalne?)
: 19 cze 2011, o 16:37
autor: 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ć?
Klasyfikacja języków (rekurencyjne czy rek. policzalne?)
: 19 cze 2011, o 17:45
autor: 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.
Klasyfikacja języków (rekurencyjne czy rek. policzalne?)
: 19 cze 2011, o 18:56
autor: 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ę.
Klasyfikacja języków (rekurencyjne czy rek. policzalne?)
: 20 cze 2011, o 17:16
autor: 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)}\).
Klasyfikacja języków (rekurencyjne czy rek. policzalne?)
: 20 cze 2011, o 17:42
autor: 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.