Jazyky, automaty a gramatiky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

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.

Požadavky:

Osnova 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.

Osnova 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.

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.

Studijní materiály:

[1] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006.

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: