Odovzdávacie domáce úlohy #1 a #2
Tieto úlohy má každý z vás vyriešiť a riešenie odovzdať v písomnej forme
do krabice pred sekretariátom KI (pavilón M, 2. poschodie)
DO PONDELKA 30. 9. 2002 8:05.
Každá z nich bude hodnotená 3 bodmi.
Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že
L, L1, L2 atď. sú ľubovoľné jazyky a h je ľubovoľný
homomorfizmus.
Zjednotenie značíme u, prienik ^, doplnok C.
Úloha #1
Zostrojte bezkontextovú gramatiku, generujúcu jazyk:
L = { ai b2i+j cj+2 | i,j >= 0 }
Dokážte správnosť svojej konštrukcie (t.j. že gramatika
generuje všetky slová tohoto jazyka a žiadne iné).
Úloha #2
Dané sú jazyky
L1, L2, ..., Ln.
Rozhodnite, či sa dá z týchto jazykov pomocou operácii zreťazenia (.)
a iterácie (*) zostrojiť jazyk
(L1 u L2 u ... u Ln)*.
Ak áno, ukážte ako, ak nie, dokážte.