Moodle FEL ČVUT
Jazyky, automaty a gramatiky
B241 - Zimní 24/25
Jazyky, automaty a gramatiky - B4B01JAG
| Kredity | 6 |
| Semestry | zimní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+2S |
Anotace
Základní pojmy teorie konečných automatů a gramatik: deterministické a nedeterministické konečné automaty,.charakterizace třídy jazyků přijímaných konečným automatem a jejich popis regulárním výrazem. Gramatiky a jazyky generované danými gramatikami s důrazem na bezkontextové gramatiky. Pojem zásobníkového automatu a jeho vztah k bezkontextovým gramatikám. Na závěr se studenti seznámí s pojmem Turingova stroje a s tím, že existují algoritmicky nerozhodnutelné problémy.
Cíle studia
Cílem studia je seznámit studenty se základy teorie formálních jazyků. Hlavními prostředky studia jsou konečné automaty a gramatiky.
Osnovy přednášek
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.
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.
Osnovy cvičení
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.
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.
Literatura
1] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006.
Požadavky
Nejsou.