foja 16.01.2006., 2. termin skusky
. (8b) Konstrukciou PDA dokazte, ze trieda bezkontextovych jazykov je uzavreta na nevymazavajuci homomorfizmus.
2. (10b) Napiste CS gramatiku, ktora generuje jazyk L={w patriace do {a,b,c}^* | #a(w)x#b(w)=#c(w)}.
3. (12b) Vyslovte a dokazte Pumpovaciu lemu pre bezkontextove jazyky. Vysvetlite, ako pomocou nej mozno dokazat, ze jazyk nie je bezkontextovy.
4. (10b) Vyslovte Nerodovu vetu. Pouzite ju na odkaz toho, ze minimalny KA rozpoznavajuci jazyk L={w patriace do {a,b}^* | #a(w) mod 3 = 0} ma 3 stavy (T.j. treba skonstruovat KA A s 3 stavmi taky, ze L=L(A) a pomocou Nerodovej vety ukazat, ze menej stavov nestaci).
5. (10b) Napiste a odovodnite algoritmus, ktory pre zadany konecny automat zisti, ci jazyk nim generovany je prazdny/konecny/nekonecny.