Języki, automaty i obliczenia/Ćwiczenia 9: Języki bezkontekstowe i ich gramatyki

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 9

Ćwiczenie 1

Określ gramatyki bezkontekstowe generujące języki:

Rozwiązanie

Ćwiczenie 2

Wykorzystując dowód lematu 1.2, napisz dla dowolnej gramatyki bezkontekstowej generującej język bez słowa pustego algorytm konstrukcji równoważnej gramatyki właściwej.

Ćwiczenie 3

Sprowadź do postaci Chomsky'ego następujące gramatyki ( jest symbolem początkowym):

Rozwiązanie punktu 1
Rozwiązanie punktu 2

Ćwiczenie 4

Sprowadź do postaci normalnej Greibach następującą gramatykę ( jest symbolem początkowym):

Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 5

Określ gramatykę bezkontekstową generującą język

Uwagi. Język jest właściwym podzbiorem języka palindromów rozważanego w ćwiczeniu 1. Porównaj otrzymane gramatyki.
Do znalezienia gramatyki generującej język zdefiniuj dwie gramatyki pomocnicze podobnie jak w punkcie 3 ćwiczenia 1.

Ćwiczenie 6

Sprowadź do postaci Chomsky'ego następujące gramatyki ( jest zawsze symbolem początkowym):

Ćwiczenie 7

Sprowadź do postaci normalnej Greibach następującą gramatykę:

Ćwiczenie 8

Sprowadź do postaci normalnej Greibach następującą gramatykę: