Popis předmětu - B4B01JAG
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://moodle.fel.cvut.cz/courses/B4B01JAG
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.
Obsah:
| 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. |
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.
Klíčová slova:
Konečný automat, gramatika,Chomského hiearchie gramatik, bezkontextová gramatika, zásobníkový automat.
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 13.11.2025 11:51:53, semestry: L/2024-5, L/2026-7, Z,L/2025-6, Z/2026-7, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |