Jazyky,automaty a gramatiky

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í:

Marie Demlová (gar.)

Cvičící:

Marie Demlová (gar.), Jiří Demel

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.

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

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Otevřená informatika - Počítačové systémy (povinný předmět programu)
• Otevřená informatika - Informatika a počítačové vědy (povinný předmět programu)
• Otevřená informatika - Softwarové systémy (povinný předmět programu)
• Otevřená informatika, před rozřazením do oborů (povinný předmět programu)