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

Jazyky, automaty a gramatiky

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B4B01JAG Z,ZK 6 2+2 česky
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. 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://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html
Rozvrh na zimní semestr 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost KN:E-107
Demlová M.
14:30–16:00
(přednášková par. 1)
Karlovo nám.
Zengerova posluchárna K1
místnost KN:E-126
Demlová M.
16:15–17:45
(přednášková par. 1
paralelka 101)

Karlovo nám.
Trnkova posluchárna K5
Út
St
Čt
místnost KN:E-301
Demel J.
14:30–16:00
(přednášková par. 1
paralelka 102)

Karlovo nám.
Šrámkova posluchárna K9
místnost KN:E-301

16:15–17:45
(přednášková par. 1
paralelka 103)

Karlovo nám.
Šrámkova posluchárna K9

Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 19. 7. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4681606.html