Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
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:
A4B01JAG
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. |
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. |
Literatura:
[1] | | J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata |
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
Poznámka:
Rozsah výuky v kombinované formě studia: 14p+6s |
Webová stránka:
http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html
Klíčová slova:
http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html
Předmět je zahrnut do těchto studijních plánů:
Stránka vytvořena 20.4.2018 17:47:30, semestry: L/2018-9, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |