Vladan Majerech - NTIN071 Automaty a gramatiky
Last Modified: 5.4.2024
Index
zápočtové písemky, odkazy,
cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5,
cvičení 7/a>
Zápočet je udělován za zápočtovou písemku, které se koná na 2. hodině od konce semestru.
Na písemkce bude zadáno 6 příkladů ...
Zápočtové písemky
Příklady zápočtových písemek z daleké minulosti, kdy byly 4 příklady z nichž 2 správně vyřešené stačily na zápočet: Podotýkám, že požadované konečné automaty byly tak malé, že dobře nakreslený graf byl přehlednější než tabulka. Ve vzorových řešeních jsou uvedeny jen tabulky (kreslení na papír je mnohem snazší než v editoru). Schválně, jestli objevíte neznámou chybu.
7.5.2003 E3 10:40-12:10 zadání řešení
12.5.2003 M4 12:20-13:50 zadání řešení (O opravitelné chybě v redukci 1) víme.)
12.5.2003 M4 14:00-15:30 zadání řešení
19.5.2003 M4 12:20-13:50 zadání řešení
19.5.2003 M4 14:00-15:30 zadání řešení
21.5.2003 E3 10:40-12:10 zadání řešení
Odkazy na obdobné stránky
moje loňské cvičeníCvičení 1
Na prvním cvičení jsme probrali „extended abstract“ toho, co budeme dělat celý rok.
Cvičení 2
Nejprve jsme zjišťovali, co dělají dané 3 3-stavové automaty, pak jsme řešili úlohu 4 stavového automatu přijímajícího $a^5$.
Ve zbytku hodiny jsme konstruovali automat počítající tenisové skóre. Ukázali jsme si přitom jazykovou konstrukci substituce (podprogramy). Pak jsme ještě automat pro jednu hru (v tenise) redukovali. Na posledním cvičení jsme ještě měli čas vytvřoit automat přijímající čísla ve dvojkové soustavě, která jsou dělitelná třemi.
Cvičení 3
Věnovali jsme se různým jazykovým konstrukcím a možnosti jejich realizace na konečných automatech (pokud existují pro původní jazyky).
Cvičení 4
Dokázali jsme si podtrhávací pumping lemma pro jazyky přijímané konečnými automaty, zadal jsem dlouhodobý domácí úkol nalézt jazyk $L$, takový, že jak pro $L$ tak pro jeho doplněk platí podrhávací pumping lemma a přitom $L$ není přijímaný konečným automatem.
Pokračovali jsme zavedením regulárních výrazů a jim odpovídajícícm jazykům. Uvědomili jsme si, že umíme vytvořit konečný automat pro všechny jazyky odpovídající základním regulárním výrazům, a pro všechny použité konstrukce máme návod jak z konečného automatu pro jazyky operandů vyvořit konečný automat pro výsledek. Víme tedy že pro každý jazyk odpovídající regulárnímu výrazu jsme schopni zkonstruovat konečný automat, který jej přijímá.
Na konci hodiny jsme si uvědomili, že pro zadaný konečný automat Floyd-Warshal algoritmus dokáže najít regulární výraz jemuž odpovídající jazyk je jazykem daného automatu.
Cvičení 5
Věnovali jsme se dvoucestným automatům (a byl zadán domácí úkol o dvoucestném automatu s kamínkem).
Cvičení 6
Věnovali jsme se procvičování konečných automatů.
Cvičení 7
Věnovali jsme se Chomskyho normální formě, pumping lemmatu pro bezkontextové gramatiky, nedeterministickým zásobníkovým automatům (přijímající koncovým stavem jsou ekvivalentní přijímající prázdným zásobníkem s jediným stavem), věnovali jsme se vztahu bezkontextových gramatik a nedeterministických zásobníkových automatů.