Jazyky, automaty a gramatiky

Garant předmětu:

Marie Demlová

Přednášející:

Marie Demlová

Cvičící:

Jiří Demel, Marie Demlová

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:

Nejsou.

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:

https://moodle.fel.cvut.cz/courses/B4B01JAG

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

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

• Otevřená informatika - Informatika a počítačové vědy 2016 (povinný předmět oboru)
• Otevřená informatika - Software 2016 (povinný předmět oboru)
• Otevřená informatika - před rozřazením do oborů (povinný předmět oboru)
• Lékařská elektronika a bioinformatika - Specializace Bioinformatika (povinně volitelný předmět)
• Otevřená informatika - Základy umělé inteligence a počítačových věd 2018 (povinný předmět zaměření)
• Otevřená informatika - Software 2018 (povinný předmět zaměření)