Automaty a gramatiky - cvičení

Rozvrh: čtvrtek od 15:40 v S6
Vyučující: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Informace o přednášce: 2/2 Zk/Z NTIN071 v SISu, na stránce k přednášce

Procvičované příklady

• Cvičení 1 - 19. 2.: Konečné automaty. Myhill-Nerodova věta.
• Cvičení 2 - 26. 2.: Pumping lemma. Homomorfismus automatů. Stavová ekvivalence, faktorizace automatů.
• Cvičení 5. 3. odpadá.
• Cvičení 3 - 12. 3.: Redukce automatů. Nedeterministické konečné automaty. Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 4 - 18. 3.: Další operace s jazyky. Regulární výrazy, převod výrazu na automat.
• Cvičení 5 - 26. 3.: Převod automatu na regulární výraz. Gramatiky.
• Cvičení 6 - 2. 4.: Pravé lineární a bezkontextové gramatiky.
• Cvičení 7 - 9. 4.: Redukce gramatiky, Chomského normální tvar. Pumping lemma pro BKJ.

Hodnocení
Na zápočet je třeba alespoň 80 bodů. V zápočtové písemce (21.5.) je možné získat max. 120 bodů, za domácí úkoly max. 9x 2 body, a další 2 body lze získat za aktivitu na cvičeních. Domácí úkoly se budou odevzdávat na papíře na cvičeních (preferováno) anebo v případě nutnosti mailem. Podrobnější informace k písemce a vzorová písemka.

Konzultace
Po cvičení, případně po domluvě mailem.