Formální jazyky a automaty
Seznam přednášek
- Úvod, abeceda, řetězece, jazyk, konečný deterministický automat (pdf)
- Vlastnosti regulárních jazyků a nedeterminismus (pdf)
- Determinizace a regulární výrazy (pdf)
- Další vlastnoti regulárních jazyků a pumping lemma (pdf)
- Minimalizace (pdf)
- Zápočtový test, ukázka práce s regexy
- Gramatiky a Chomského hierarchie (pdf)
Studijní materiály ke cvičením
- Odkaz na pdf.
- Na cvičeních budeme řešit úkoly z těchto materiálů, proto Vám doporučuji si dokument vytisknout a na cvičeních si do něj doplňovat řešení úkolů. Vyplněný dokument Vám může posloužit i později, například až se budete připravovat na státnice.
- Domácí úkoly na konci dokumentů jsou dobrovolné a nebudu je kontrolovat. Nicméně doporučuji každému si na nich vyzkoušet jestli dané látce rozumíte a zda dokážete úkoly vyřešit samostatně.
Zápočet
Zápočet se skládá ze dvou částí, tj. dvou zápočtových testů: první na regulární jazyky, druhý na bezkontextové jazyky. Z každé části potřebujete získat aspoň 50% bodů, přičemž každý test si budete moci jednou opravit. Předběžný harmonogran testů:
- První test se bude psát na přednášce 6. týden semestru, tedy v úterý 19.3.,
- druhý test se bude psát na přednášce 12. týden semestru, tedy v úterý 30.4.,
- opravné testy se budou psát někdy v prvním týdnu zkouškového období.