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
| B4B01JAG | Jazyky, automaty a gramatiky | ||
|---|---|---|---|
| Role: | PO, PV, PZ | Rozsah výuky: | 2P+2S |
| Katedra: | 13101 | Jazyk výuky: | CS |
| Garanti: | Demlová M. | Zakončení: | Z,ZK |
| Přednášející: | Demlová M. | Kreditů: | 6 |
| Cvičící: | Demel J., Demlová M. | Semestr: | Z |
Webová stránka:
https://moodle.fel.cvut.cz/courses/B4B01JAGAnotace:
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ů:
| Plán | Obor | Role | Dop. semestr |
| MPBIO1_2018 | Bioinformatika | PV | – |
| BPOI1_2018 | Základy umělé inteligence a počítačových věd | PZ | 5 |
| BPOI1_2016 | Informatika a počítačové vědy | PO | 5 |
| BPOI_BO_2016 | Před zařazením do oboru | PO | 5 |
| BPOI3_2016 | Software | PO | 5 |
| BPOI3_2018 | Software | PZ | 5 |
| Stránka vytvořena 14.10.2024 17:51:05, semestry: Z/2025-6, Z/2024-5, L/2023-4, L/2024-5, 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) |