Detail předmětu
Teoretická informatika 1
TI1 Ak. rok 2004/2005 zimní semestr 6 kreditů
Význam a aplikace teorie formalních jazyků, operace nad jazyky, reprezentace jazyků, způsoby reprezentace formálních jazyků, gramatiky, Chomského klasifikace gramatik a formálních jazyků, jazyky přijímané konečnými automaty, vztah jazyků typu 3 a jazyků přijímaných konečnými automaty, regulární množiny a regulární výrazy, minimalizace konečného automatu, vlastnosti regulárních jazyků, bezkontextové gramatiky, problém syntaktické analýzy, transformace bezkontextových gramatik, zásobníkové automaty, ekvivalence jazyků typu 2 a jazyků přijímaných zásobníkovými automaty, vlastnosti bezkontextových jazyků, Petriho sítě.
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 12 hod. cvičení
- 2 hod. pc laboratoře
- 12 hod. projekty
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
Teoretické znalosti využívané v problémech konstrukce překladačů, modelování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.
Cíle předmětu
Osvojení základů teorie formálních jazyků využívaných v konstrukci překladačů a v modelování výpočetních systémů.
Požadované prerekvizitní znalosti a dovednosti
Nejsou žádné prerekvizity.
Osnova přednášek
- Úvod, organizace předmětu, význam a aplikace teorie formalních jazyků, příklady jazyků a jejich specifikace.
- Formální jazyky, pojmy abeceda, řetězec, zřetězení, operace nad jazyky, algebra jazyků jako polookruh.
- Reprezentace jazyků, problém reprezentace, způsoby reprezentace formálních jazyků.
- Gramatiky, definice gramatiky, relace derivace, větná forma a jazyk generovaný gramatikou, Chomského klasifikace gramatik a formálních jazyků, ilustrační příklady.
- Jazyky přijímané konečnými automaty, definice konečného nedeterministického automatu, konfigurace automatu, relace přechodu, jazyk přijímaný konečným automatem, vztah deterministických a nedeterministických konečných automatů, vztah jazyků typu 3 a jazyků přijímaných konečnými automaty, ilustrační příklady.
- Regulární množiny a regulární výrazy, definice, algebra regulárních výrazů (identity), rovnice nad regulárními výrazy, vztah regulárních množin a jazyků typu 3, ilustrační příklady. Rozšířený konečný automat, převod regulárního výrazu na ekvivalentní deterministický konečný automat, ilustrační příklady.
- Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu ilustrační příklady.
- Vlastnosti regulárních jazyků, strukturální vlastnosti, Pumping theorem pro regulární jazyky, uzávěrové vlastnosti, rozhodnutelné problémy regulárních jazyků, ilustrační příklady a příklady k samostatnému řešení.
- Bezkontextové gramatiky, definice, levá a pravá derivace, víceznačnost gramatik, rekurze, problém syntaktické analýzy, klasifikace syntaktických analyzátorů, ilustrační příklady a příklady k samostatnému řešení.
- Transformace bezkontextových gramatik, ekvivalence bezkontextových gramatik, odstranění zbytečných symbolů, odstranění e-pravidel, odstranění jednoduchých pravidel, převod na vlastní gramatiku, odstranění levé rekurze, ilustrační příklady.
- Zásobníkové automaty, definice, varianty, ekvivalence jazyků typu 2 a jazyků přijímaných zásobníkovými automaty, deterministické zásobníkové automaty a deterministické bezkontextové jazyky, ilustrační příklady.
- Vlastnosti bezkontextových jazyků, normální tvary bezkontextových gramatik, Greibachové a Chomského normální forma, pumping theorem pro bezkontextové jazyky, uzávěrové vlastnosti bezkontextových jazyků, rozhodnutelné a nerozhodnutelné problémy bezkontextových jazyků, ilustrační příklady.
- Petriho sítě, definice, stavový prostor a přechodová funkce Petriho sítě, lineární algebraická reprezenatce Petriho sítě, ilustrační příklady.
Osnova numerických cvičení
- Operace nad jazyky, gramatiky, jejich klasifikace.
- Vzájemné převody mezi gramatikami typu 3, konečnými automaty a regulárními výrazy.
- Minimalizace konečných automatů, vlastnosti regulárních jazyků.
- Konstrukce bezkontextových gramatik, derivační stromy.
- Transformace bezkontextových gramatik.
- Konstrukce zásobníkových automatů, vlastnosti bezkontextových jazyků.
Osnova počítačových cvičení
- Petri net tool PESIM.
Průběžná kontrola studia
Udělení zápočtu je podmíněno absolvováním polosemestrální písemné zkoušky a ziskem minimálně 25 bodů za bodované aktivity v průběhu semestru (půlsemestrální zkouška, domací úlohy).
Kontrolovaná výuka
Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů