Formální jazyky a automaty

Zkouška

• Zkouškové otázky naleznete zde.
• Zkouška se skládá ze 2 otázek: jedna na definice a pojmy, druhá s důkazem.
• Před zkouškou budete mít 15-20 minut na přípravu.
• Formální oblečení není třeba.

Seznam přednášek

• 11.2. Regulární jazyky, pdf + praktická ukázka v pythonu
• 18.2. Konečné automaty, pdf
• 25.2. Nedeterminismus, pdf
• 4.3. Ekvivalence automatů a regulárních výrazů, pdf
• 11.3. Minimalizace, pdf
• 18.3. Další vlastnosti regulárních jazyků a pumping lemma, pdf
• 25.3. První zápočtový test
• 1.4. Gramatiky a Chomského hierarchie, pdf
• 8.4. Chomského normální forma a CYK, pdf
• 15.4. Zásobníkové automaty, pdf
• 22.4. Vlastnosti bezkontextových jazyků, pdf
• 29.4. Druhý zápočtový test + Gramatiky typu 0 a 1, 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 7. týden semestru, tedy v úterý 25.3.,
• druhý test se bude psát na přednášce 12. týden semestru, tedy v úterý 29.4.,
• opravné testy se budou psát někdy v prvním týdnu zkouškového období.