|
Vyučující
|
-
Hrubý Filip, Mgr. MSc.
-
Skrbek Miroslav, Ing. Ph.D.
|
|
Obsah předmětu
|
Obsah přednášky: 1. Potřebné partie z diskrétní matematicky 2. Symboly, řetězy, jazyky, gramatiky 3. Regulární jazyky: regulární výrazy, konečné automaty a regulární gramatiky 4. Vlastnosti regulárních jazyků, pumpovací lemma 5. Bezkontextové gramatiky a jazyky 6. Syntaktická analýza: derivační strom, algoritmy, LL gramatiky 7. Zjednodušování bezkontextových gramatik, normální formy Chomskyho a Greibachové 8. Zásobníkové automaty 9. Vlastnosti bezkontextových jazyků 10. Turingův stroj 11. Turingova hypotéza a pojem algoritmu 12. Modifikace Turingova stroje, univerzální Turingův stroj 13. Lineárně omezený automat 14. Rekurzivně spočetné jazyky, Chomskyho hierarchie 15. Meze možností algoritmických výpočtů, problém zastavení Turingova stroje Obsah cvičení: Cvičení rozšiřují a doplňují látku přednášek o praktické problémy zaměřené především na syntaktickou analýzu.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž)
- Účast na výuce
- 56 hodin za semestr
- Domácí příprava na výuku
- 56 hodin za semestr
- Příprava na zkoušku
- 38 hodin za semestr
|
|
Výstupy z učení
|
Kurs se zabývá teorií formálních jazyků a automatů se zaměřením na syntaktickou analýzu.
Studenti získají základní přehled o hierarchii formálních jazyků a podrobnější znalosti o regulárních a bezkontextových jazycích. To jim usnadní návrh vlastních jednodušších jazyků a výběr vhodných softwarových nástrojů.
|
|
Předpoklady
|
Základní znalosti diskrétní matematiky (množiny, funkce, grafy, stromy)
|
|
Hodnoticí metody a kritéria
|
Písemná zkouška, Průběžné hodnocení
Za semestr může student získat maximálně 100 bodů ve struktuře 55 bodů zkouška, 45 bodů cvičení. Za semestr musí student získat minimálně 25 bodů z průběžné práce ve cvičení, jejíž součástí jsou testy, které nelze opakovat. Pro úspěšné absolvování předmětu musí student dosáhnout minima počtu bodů za cvičení a celkový součet bodů za cvičení i zkoušku musí být >= 50 bodů., přičemž ve zkoušce musí student dosáhnout alespoň 25 bodů. Pokud není některá z těchto podmínek splněna, student neuspěl. Detailní informace o bodech z průběžných prací a hodnocení jsou vyhlášeny na platformě elearning stránkách předmětu pro daný rok.
|
|
Doporučená literatura
|
-
Chytil, M. Automaty a gramatiky. Praha: SNTL, 1984.
-
Linz, P. Formal Languages and Automata. Fifth Edition. Sudbury:Jones and Bartlett, 2012. ISBN 978-1-4496-1552-9.
-
Melichar B. et al. Jazyky a překlady: Cvičení. Skriptum FEL ČVUT. Praha: Nakladatelství ČVUT, 2004. ISBN 80-01-03031-8.
-
Melichar, B. Jazyky a překlady. Skriptum FEL ČVUT, 2. vydání. Praha: Nakladatelství ČVUT, 2003. ISBN 80-01-02776-7.
|