Konečný automat a jazyky rozpoznatelné KA
2. Deterministické a nedeterministické KA
3. Zobecněné nedeterministické KA a třída jazyků rozpoznatelných KA
4. Uzávěrové vlastnosti třídy jazyků rozpoznatelných KA
5. Regulární jazyky, regulární výrazy, jejich vztah k jazykům rozpoznatelným konečnými automaty
6. Konstrukce konečných automatů pro regulární výrazy.
7. Algoritmus redukce konečných automatů, ekvivalence KA
8. Bezkontextové gramatiky a jazyky, regulární gramatiky a jazyky
9. Nevypouštějící a redukované gramatiky, kanonická odvození, jednoznačné gramatiky
10. Lemma o vkládání (pumping lemma) a její využití pro důkazy zařazení jazyků do Chomského hierarchie.
11. Zásobníkové automaty, vztah k bezkontextovým jazykům
12. Turingovy stroje - definice, deterministické, nedeterministické, Univerzální Turingovy stroje.
- Učitel: Hashim Habiballa