Moodle FEL ČVUT
Jazyky,automaty a gramatiky
B242 - Letní 2024/2025
Tento předmět se nenachází v Moodle. Na jeho domovskou stránku se můžete dostat pomocí tlačítka "Stránka kurzu (mimo Moodle)" vpravo (pokud existuje).
Jazyky,automaty a gramatiky - A4B01JAG
| Kredity | 6 |
| Semestry | zimní |
| Zakončení | Zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2+2 |
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. Vztah bezkontextových gramatik a
zásobníkových automatů. Pojem Turingova stroje a seznámení studentů s
tím, že existují algoritmicky nerozhodnutelné problémy.
\\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4B01JAG
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. Vztah bezkontextových gramatik a
zásobníkových automatů. Pojem Turingova stroje a seznámení studentů s
tím, že existují algoritmicky nerozhodnutelné problémy.
\\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4B01JAG
Cíle studia
None
Osnovy přednášek
1. Abeceda, slova nad abecedou, zřetězení slov, jazyk.
2. Deterministický konečný automat, stavový diagram.
3. Jazyk přijímaný konečným automatem, Nerodova věta.
4. Nedeterministické konečné automaty.
5. Ekvivalence deterministických a nedeterministických konečných automatů.
6. Regulární výrazy a regulární jazyky, Kleeneova věta.
7. Algoritmická složitost úloh souvisejících s regulárními jazyky
8. Gramatiky, regulární gramatiky a bezkontextové gramatiky,
bezkontextové jazyky.
9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
10. Vlastnosti bezkontextových gramatik, lemma o vkládání.
Uzavřenost třídy bezkontextových jazyků.
11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky.
12. Turingovy stroje.
13. Algoritmicky neřešitelné úlohy.
14. Rezerva.
2. Deterministický konečný automat, stavový diagram.
3. Jazyk přijímaný konečným automatem, Nerodova věta.
4. Nedeterministické konečné automaty.
5. Ekvivalence deterministických a nedeterministických konečných automatů.
6. Regulární výrazy a regulární jazyky, Kleeneova věta.
7. Algoritmická složitost úloh souvisejících s regulárními jazyky
8. Gramatiky, regulární gramatiky a bezkontextové gramatiky,
bezkontextové jazyky.
9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
10. Vlastnosti bezkontextových gramatik, lemma o vkládání.
Uzavřenost třídy bezkontextových jazyků.
11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky.
12. Turingovy stroje.
13. Algoritmicky neřešitelné úlohy.
14. Rezerva.
Osnovy cvičení
1. Abeceda, slova nad abecedou, zřetězení slov, jazyk.
2. Deterministický konečný automat, stavový diagram.
3. Jazyk přijímaný konečným automatem, Nerodova věta.
4. Nedeterministické konečné automaty.
5. Ekvivalence deterministických a nedeterministických konečných automatů.
6. Regulární výrazy a regulární jazyky, Kleeneova věta.
7. Algoritmická složitost úloh souvisejících s regulárními jazyky.
8. Gramatiky, regulární gramatiky a bezkontextové gramatiky,
bezkontextové jazyky.
9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
10. Vlastnosti bezkontextových gramatik, lemma o vkládání. Uzavřenost
třídy bezkontextových jazyků.
11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky,
algoritmus CYK.
12. Turingovy stroje.
13. Algoritmicky neřešitelné úlohy.
2. Deterministický konečný automat, stavový diagram.
3. Jazyk přijímaný konečným automatem, Nerodova věta.
4. Nedeterministické konečné automaty.
5. Ekvivalence deterministických a nedeterministických konečných automatů.
6. Regulární výrazy a regulární jazyky, Kleeneova věta.
7. Algoritmická složitost úloh souvisejících s regulárními jazyky.
8. Gramatiky, regulární gramatiky a bezkontextové gramatiky,
bezkontextové jazyky.
9. Zásobníkové automaty a jejich vztah k bezkontextovým jazykům.
10. Vlastnosti bezkontextových gramatik, lemma o vkládání. Uzavřenost
třídy bezkontextových jazyků.
11. Algoritmy pro řešení některých úloh pro bezkontextové jazyky,
algoritmus CYK.
12. Turingovy stroje.
13. Algoritmicky neřešitelné úlohy.
Literatura
[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata
Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001
Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001
Požadavky
Diskrétní matematika nebo Matematika pro informatiku.
Podrobné informace: http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html
Podrobné informace: http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html