1. |
|
Abeceda, slova nad abecedou, zřetězení slov, jazyk. |
2. |
|
Deterministický konečný automat a jeho stavový diagram. Jazyk přijímaný konečným automatem. Regulární jazyky. |
3. |
|
Lemma o vkládání a Nerodova věta. Redukce konečného automatu. |
4. |
|
Nedeterministické konečné automaty. Podmnožinová konstrukce. Uzavřenost třídy jazyků přijímaných konečným automatem na sjednocení, zřetězení a Kleeneho operaci. |
5. |
|
Regulární výrazy. Vztah regulárních jazyků a regulárních výrazů ? Kleeneho věta. |
6. |
|
Algoritmická složitost úloh souvisejících s regulárními jazyky. Pojem gramatiky. |
7. |
|
Chomského hierarchie tříd jazyků generovaných gramatikou. Regulární gramatiky a regulární jazyky. Bezkontextové gramatiky a bezkontextové jazyky. |
8. |
|
Lemma o vkládání. Redukce bezkontextové gramatiky. |
9. |
|
Zásobníkové automaty a jazyky přijímané zásobníkovými automaty prázdným zásobníkem a koncovým stavem. |
10. |
|
Vlastnosti třídy bezkontextových jazyků. |
11. |
|
Deterministické zásobníkové automaty a jejich vlastnosti. Třída deterministických jazyků a třída bezprefixových jazyků. |
12. |
|
Seznámení sTuringovými stroji. |
13. |
|
Krátké seznámení s nerozhodnutelnými jazyky a algoritmicky neřešitelnými úlohami. |