Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

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 2P+2S česky
Garant předmětu:
Marie Demlová
Přednášející:
Marie Demlová
Cvičící:
Jiří Demel, Marie Demlová
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://moodle.fel.cvut.cz/courses/B4B01JAG
Rozvrh na zimní semestr 2023/2024:
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 FS_KN:A-312
Demlová M.
14:30–16:00
(přednášková par. 1)
Karlovo nám.
Posluchárna FS A:312 - záp.
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
místnost KN:E-107
Demlová M.
14:30–16:00
(přednášková par. 1)
Karlovo nám.
Zengerova posluchárna K1
Ú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-127
Demel J.
16:15–17:45
(přednášková par. 1
paralelka 103)

Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-112
Demel J.
14:30–16:00
(přednášková par. 1
paralelka 102)

Karlovo nám.
Cvičebna Vyčichlova

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