Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Jazyky,automaty a gramatiky

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
AD4B01JAG Z,ZK 6 14+6 česky
Podmínkou zápisu předmětu je, že student získal v předchozích semestrech zápočet z následujících předmětů:
Diskrétní matematika (AD4B01DMA)
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. 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

Požadavky:

Diskrétní matematika nebo Matematika pro informatiku.

Podrobné informace: http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html

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

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

Cíle studia:
Studijní materiály:

[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata

Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6s

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ů:
Platnost dat k 9. 12. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1201506.html