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:PZ, PO, PV 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/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ů:

Plán Obor Role Dop. semestr
BPOI3_2018 Software PZ 3
BPOI1_2018 Základy umělé inteligence a počítačových věd PZ 5
MPBIO1_2018 Bioinformatika PV
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


Stránka vytvořena 29.3.2024 12:50:51, semestry: Z/2024-5, Z,L/2023-4, 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)