ČeskyEnglish

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 Rozsah výuky:2+2
Garanti:Demlová M. Role:PO Zakončení:Z,ZK
Vyučující:Demlová M.
Zodpovědná katedra:13101 Kreditů:6 Semestr:Z

Anotace:

Základní pojmy teorie konečných automatů a gramatik: deterministické a nedeterministické 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.

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.
13. Krátké seznámení s nerozhodnutelnými jazyky a algoritmicky neřešitelnými úlohami.

Literatura:

[1] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006.

Požadavky:

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BPOI3_2016 Software PO 5
BPOI_BO_2016 Před zařazením do oboru PO 5
BPOI1_2016 Informatika a počítačové vědy PO 5


Stránka vytvořena 23.5.2017 18:00:46, semestry: Z,L/2016-7, Z,L/2017-8, Z/2018-9, 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)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.