Automaty a gramatiky – zkouška LS 2008
Písemná část trvá 2 hodiny čistého času. Nejprve se píše zaškrtávací test, pokud získáte dostatečný počet bodů (oficiálně 19, ale dva jsme prošli s 18, otázek je celkem asi něco pod třicet), dostanete zadání vlastní písemky. Skóre z testu ovlivňuje i (případnou) známku ze zkoušky (to říkal přímo Barták), nicméně jsem živoucím důkazem, že i z 18 bodů lze vymáčknout dvojku.
Nějaká stará zadání testů nalezená na fórech (nebojte: 1. dostanete jiné, 2. vyznačené odpovědi jsou někdy špatně, 3. půlka stejně nejde přečíst, ale aspoň něco se bude krýt;)):
Já jsem se teda z těchhle testů moc nepřipravoval (asi chyba), ale stejně jsem měl i otázky, které tam nebyly. Vzpomínám si třeba na:
- A1 = (Q1, X, δ1, q1, F1); A2 = (Q2, X, δ2, q2, F2); A = (Q1 x Q2, X, δ, (q1, q2), Q1 x Q2), δ(p,q), x) = (δ1(p,x), δ2(q,x)). Následovaly možnosti, čemu se rovná L(A). Nerovná se ale ničemu nabízenému, protože jako koncové stavy má Q1 x Q2 (tzn. všechny).
- Jakým jazykem se dá popsat regulární výraz: možnosti regulárním, bezkontextovým, lineárním a nevímjakýmještě. Formulace byla možná ještě trochu jiná. Fígl je ale v tom uvědomit, že jde o jazyk, jehož slovy jsou regulární výrazy, nikoli jazyk, který se dá popsat regulárním výrazem. Regulární jazyk tedy není správná odpověď. Tuším, že o takovém jazyce se na přednášce mluvilo, takže ta otázka není úplně neoprávněná, navíc je jednoduchá, pokud ji pochopíte...
- (Pak taky něco týkající se Turingova stroje, automatu se dvěma zásobníky, dvěma čtecími hlavami, dvěma páskami a nevímčímještě, možná si někdo vpomene konkrétně. Ale byli mezi tím i ne zcela triviální věci, třeba ten automat se dvěma zásobníky má zřejmě sílu Turingova stroje.)
A moje zadání písemky vypadalo takhle nějak:
Je dán jazyk L = {aibjck | i ≤ j ≤ k}. Zkonstruuj kontextovou gramatiku G, tž. L = L(G). Dokaž, že pro daný jazyk nejde zkonstruovat kontextová gramatika. Definuj kontextovou gramatiku, monotónní gramatiku, vztah mezi nimi. Dokaž. (Tzn. jednalo se o to, že z pro každou monotónní gramatiku lze zkonstruovat kontextovou gramatiku generující týž jazyk.)
— Adam (zkouška 27. května)
Moje vypadalo zase takhle:
Zkonstruujte redukovany deterministicky konecny automat, ktery prijima slova z jazyka {a,b}*, ktera na konci maji skupinu symbolu a – alespon vsak dvou -, predchazenou symbolem b. Co to je redukovany automat? Co to je ekvivalence stavu? Dokazte vsechna tvrzeni a vety, ktere jste pouzili pri tvorbe automatu.
— Cestmir (zkouska 27. kvetna)
Je dán jazyk L = {0n1n | 0 ≤ n ≤ m ≤ 2n}. Zkonstruuj bezkontextovou gramatiku G, tž. L = L(G). Definuj regulární gramatiku, bezkontextovou gramatiku. Dokaž, že pro daný jazyk nejde zkonstruovat regulární gramatika. Dokaž věty, které jsi použil. (Tzn. Nerodovu větu.)
(od Jakuba Melky taky z 27. května)
Po dopsání následuje přesun a ústní zkoušení, které probíhá příjemně, ale zase nic nedostanete zadarmo. Zkoušení trvá v průměru poměrně dlouho, za hodinu se vyzkouší odhadem nejvýše pět lidí, spíš méně. Pokud jste něco při psaní písemky nedokázali, vaše gramatika negeneruje to, co má, nebo jste chybně formulovali tvrzení a následně dokazovali něco jiného, budete mít druhou šanci. O testu se, ani co jsem viděl u ostatních, nebavil. Ukázal mi ho až na požádání.
Já jsem měl jazyk L = {u . uR . u | u patří do {0, 1}* }. Měl jsem tento jazyk zařadit do co nejmenší třídy Chomského hierarchie a dokázat, proč nepatří do nižší třídy. Taktéž jsem měl napsat a dokázat tvrzení, které mi pomohlo určit, že tento jazyk nepatří níže (čili pumping lemma pro BKJ).
Podle mě to nebylo zase tak těžké zadání, ale bylo toho dost na docela málo času. Nestihl jsem napsat k tomuto jazyku gramatiku, ale doc. Barták mi ji dal dopsat na ústní části. Stejně jako Adam jsem důkazem toho, že i z 18 bodů se dá udělat za 2. Na ústní je Barták opravdu v pohodě. Ale ty testy jsou fakt drsné.
— Mates (zkouška taktéž 27.května)
nečitelné testy