Moodle FEL ČVUT
Jazyky, automaty a gramatiky
B241 - Zimní 2024/2025
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.
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.
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
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
None
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.
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.
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
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
Podrobné informace: http://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html