Toto je tzv. shluknutý kurz. Skládá se z několika samostatných předmětů, které sdílejí výukové materiály, úkoly, testy apod. Níže si můžete zobrazit informace o jednotlivých předmětech tvořících tento shluk.

Jazyky, automaty a gramatiky - B4B01JAG

Hlavní kurz
Kredity 6
Semestry zimní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 2P+2S
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.
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.
Osnovy 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.
Osnovy 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.
Literatura
1] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006.
Požadavky
Nejsou.

Jazyky,automaty a gramatiky - A4B01JAG

Kredity 6
Semestry zimní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 2+2
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
Cíle studia
Žádná data.
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