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:

A₁ = (Q₁, X, δ₁, q₁, F₁); A₂ = (Q₂, X, δ₂, q₂, F₂); A = (Q₁ x Q₂, X, δ, (q₁, q₂), Q₁ x Q₂), δ(p,q), x) = (δ₁(p,x), δ₂(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á Q₁ x Q₂ (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.)

Letošní zadání

Je dán jazyk L = {aⁱb^jc^k | 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)

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 = {0ⁿ1ⁿ | 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)

Já jsem měl jazyk L = {u . u^R . 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).

— Mates (zkouška taktéž 27.května)

Jako priklad jsem dostal jazyk L = { w patří do {a,b,c}*, pocet acek=pocet becek= pocet cecek (nikoli aⁱbⁱcⁱ) }
stejne jako martin zaradit do chomskeho hierarchie a dokazat proc neni niz a co mi to pomohlo rozhodnout.

— Karl (zkouška 23.května)

Sestrojte redukovany konecny automat rozpoznavajici jazyk L={u | u se sklada z {a,b}*, obsahuje 3k béček a neobsahuje 3k+1 áček}. Definujte kongruenci automatu a podilovy automat. Uvedte tvrzeni o konstrukci podiloveho automatu a dokazte ho.

— h. (zkouška 4.června)

Definujte linearni gramatiky, zaradte jazyky jimi generovane do Chomskeho hierarchie,..., dokazte, ze pro ne plati nasledujici lemma. Dale bylo popsane lemma napadne pripominajici PL pro BKJ, ale s tvrzenim nikoli |vwx| < q, ale |uvxy| < p.

— jkt 4. cervna

Zařadit jazyk {ww|w patri do {0,1}*} do Chomského hierarchie (= kontextový jazyk), dokázat, že nepatří níž, a dokázat větu, kterou jsme použili (bezkontextové pumping lemma).

— bohous

Poznámky ke zkoušce a k zadáním

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í. Adam

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

Já jsem měl teda z testu 23 bodu. Učil jsem se z (jednoho) lonskeho testu, u kazde otazky jsem si rikal co by se stalo kdyby tam nebylo to a nebo bylo neco navic.
Kdyz jsem prisel na neco v cem jsem si nebyl prilis jisty, nasel jsem si to ve slajdech. Asi bych to doporucil pro uspesne napsani testu ikdyz kazdemu to vyhovuje jinak.
gramatiku jsem mel hned, s dukazem pumping lematu pro BKJ jsem trochu bojoval, ideologicky jsem to mel vlastne uplne spravne, bartakovi se tam nezdalo par detailu okolo vysky stromu, delce slova v zavislosti na delce derivace. rekl mi narovinu ze ted je to na dvojku, a jestli chci tak ze mi da jednicku kdyz poradne promyslim ten dukaz do detailu. Spokojil jsem se s dvojkou. Karl

Test mi prisel tezsi, nez ty ktere jsem si zkousel na webu. U dost otazek jsem si nebyl jistej, jestli je mam spravne nebo ne, nakonec jsem nastesti par spravne mel -> 23 bodu.
Otazka mi hodne nesedla, tu kongruenci automatu jsem si presne nepamatoval a o cem presne hovori to tvrzeni jsem taky netusil, takze jsem dlouho vymejslel a varil, ale nakonec jsem neco vymyslel. Protoze toho bylo malo a priznal jsem, ze se mi otazka vubec nelibila, dostal jsem jako doplnujici otazku ekvivalenci stavu a jeji zjistovani. Posleze za 2.
h.

I kdyz clovek tvrdi, ze linearni grmatiky generuji to same, co BKJ (a dokonce to “dokaze” a “podari” se mu vygenerovat linearni gramatikou spravne uzavorkovani :) ), da se z toho dostat jednicka. --jkt