Języki, automaty i obliczenia/Test 11: Automat ze stosem

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wskaż języki bezkontekstowe, które nie są regularne:


Wskaż zdania prawdziwe:

Istnieje gramatyka reularna generująca język Dycka.

Język Dycka jest bezkontekstowy i nie jest regularny.

Istnieje automat skończenie stanowy rozpoznający język Łukasiewicza.

Język Łukasiewicza da się opisać wyrażeniem regularnym.

Istnieje gramatyka bezkontekstowa bez symboli bezużytecznych generująca język Dycka.


Wskaż języki, które nie są bezkontekstowe:


Dana niech będzie gramatyka ( jest symbolem początkowym):

Wskaż, które z poniższych słów należą do języka generowanego tą gramatyką:


Wskaż gramatyki niejednoznaczne:

, , , , ,

, , , , ,

, ,

, , , , , , ,

, , , , ,


Gramatyka , gdzie , , , , , , , :

generuje język

generuje język

jest równoważna gramatyce , gdzie , , , , , , ,

jest jednoznaczna

generuje język , gdzie jest automatem skończenie stanowym takim, że , , , , , , .


Wskaż zdania prawdziwe:

każda gramatyka regularna jest jednoznaczna

każdy język jednoznaczny jest deterministyczny

każdy język regularny jest jednoznaczny

każdy język deterministyczny jest jednoznaczny

język jest jednoznaczny wtw gdy jest deterministyczny


Wskaż zdania prawdziwe:

Każda gramatyka w postaci normalnej Chomsky'ego jest bezkontekstowa.

Jeśli gramatyka bezkontekstowa ma produkcji, to równoważna jej gramatyka w postaci normalnej Greibach ma co najwyżej produkcji.

Każdą gramatykę bezkontekstową można przekształcić do postaci normalnej Greibach.

Żadna gramatyka w postaci normalnej Greibach nie jest regularna.

Każda gramatyka w postaci normalnej Chomsky'ego jest właściwa.


Wskaż zdania prawdziwe:

Każdy automat ze stosem akceptujący przez pusty stos posiada równoważny automat ze stosem akceptujący przez stany końcowe.

Każdy język bezkontekstowy jest akceptowany przez pusty stos przez jednostanowy automat ze stosem.

Każdy automat ze stosem, w którym wielkość stosu jest ograniczona przez pewną stałą, jest równoważny pewnemu automatowi skończenie stanowemu.

Każdy automat ze stosem posiada równoważny deterministyczny automat ze stosem.

Każdy automat ze stosem akceptujący przez stany końcowe posiada równoważny automat ze stosem akceptujący przez pusty stos.


Rodzina języków bezkontekstowych jest zamknięta ze względu na:

homomorfizm

iloczyn mnogościowy

uzupełnienie

gwiazdkę Kleene'ego

katenację


Dane są dwie gramatyki: dla , gdzie

Wówczas:

jest językiem skończonym


Niech będzie językiem bezkontekstowym. Wskaż problemy rozstrzygalne:

nieskończoność

równoważność dwóch gramatyk bezkontekstowych

jednoznaczność gramatyki bezkontekstowej


Niech , . Wówczas:


Wskaż języki deterministyczne:


Wskaż języki niejednoznaczne:


Automat ze stosem , gdzie , , , , , , , , , , , , , :

rozpoznaje język

rozpoznaje język

rozpoznaje język

jest automatem deterministycznym

rozpoznaje język


Niech . Wskaż problemy nierozstrzygalne w klasie :

jednoznaczność

nieskończoność


Automat ze stosem , gdzie , , , , , , , , , :

rozpoznaje język

rozpoznaje język

rozpoznaje język

jest automatem deterministycznym

rozpoznaje język


Algorytm Cocke'a-Youngera-Kasamiego:

sprawdza, czy słowo należy do języka bezkontekstowego

działa w czasie

jest niedeterministyczny

może dostać na wejście dowolną gramatykę bezkontekstową

działa w oparciu o zasadę programowania dynamicznego