|
Vyučující
|
-
Masopust Tomáš, doc. RNDr. Ph.D., DSc.
-
Balun Jiří, Mgr.
|
|
Obsah předmětu
|
Základní pojmy: formální jazyky, hierarchie gramatik a jazyků. Konečné automaty: konečné deterministické a nedeterministické automaty, jejich rozšíření, varianty a aplikace. Regulární gramatiky a jazyky: vztah ke konečným automatům, uzávěrové vlastnosti regulárních jazyků, kritéria regularity, minimalizace konečných automatů. Regulární výrazy a jejich aplikace: standardní regulární výrazy, rozšířené regulární výrazy, aplikace pro vyhledávání v textu, vybrané problémy. Bezkontextové jazyky: popis a vlastnosti, derivační stromy, vlastnosti bezkontextových jazyků a vztah k regulárním jazykům. Zásobníkové automaty: varianty, vztah k bezkontextovým jazykům, syntaktická analýza shora-dolů a zdola-nahoru, deterministické zásobníkové automaty.
|
|
Studijní aktivity a metody výuky
|
Přednášení, Demonstrace
- Příprava na zápočet
- 10 hodin za semestr
- Příprava na zkoušku
- 35 hodin za semestr
|
|
Výstupy z učení
|
Studenti se seznámí se základními pojmy z formálních jazyků.
1. Znalost Popiš základní generativní a analytické formalismy pro jazyky.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Písemná zkouška
Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.
|
|
Doporučená literatura
|
-
Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston.
-
LAWSON. (2003). Finite Automata. Chapman & Hall/CRC.
-
Linz, P. (2016). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers, Inc.
-
Melichar, B. (2003). Jazyky a překlady. Skriptum, přepracované 2. vydání. Vydavatelství ČVUT, Praha.
-
Simovici D. A., Tenney R. L. (1999). Theory of Formal Languages with Applications. World Scientific, Singapore.
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|