Languages and Automata

Zkratka předmětu KMI/LA
Název předmětu Languages and Automata
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/LA
Název Languages and Automata
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 2 HOD/TYD Cvičení 2 HOD/TYD
Vyučovací jazyk angličtina
Nahrazovaný předmět
Vyloučené předměty
Podmiňující
Způsob zakončení Zkouška
Forma zakončení Kombinovaná
Zápočet před zkouškou Ano
Vyučovaný semestr Letní
Cíle předmětu (anotace)

Kurz je úvodem do teorie konečných automatů a formálních jazyků s důrazem na algebraickou teorii konečných automatů. Jsou prezentovány základní pojmy, vztahy a konstrukce této teorie.

Požadavky na studenta

Každotýdenní studentova práce je řízena v prostředí LMS Moodle, v němž student vypracuje v průběhu semestru celkem 12 domácích úkolů. U závěrečného testu se vyžaduje úspěšnost aspoň 55%.

Obsah

Tematické celky:
1. Algebra slov nad danou abecedou, definice jazyka, operace s jazyky.
2. Deterministický konečný automat., Mooreův a Mealyho automat.
3. Nedeterministický konečný automat.
4. Automatové konstrukce.
5. Regulární jazyky, regulární výrazy.
6. Automaty a gramatiky.
7. Zásobníkový automat.
8. Bezkontextové gramatiky.
9. Konstrukce derivačních stromů.
10. Aplikace bezkontextových gramatik.
11. Kontextové gramatiky.
12. Turingův stroj.
13. Shrnutí - Chomského hierarchie formálních jazyků.

Předpoklady - další informace k podmíněnosti studia předmětu

Základy diskrétní matematiky.

Získané způsobilosti

Student aktivně ovládá a používá základní pojmy a konstrukce teorie konečných automatů. Orientuje se v Chomského hierarchii formálních jazyků. Komunikuje v anglickém jazyce.

Garanti a vyučující
  • Garanti: doc. Ing. Ladislav Beránek, CSc.
  • Přednášející: doc. Ing. Ladislav Beránek, CSc., RNDr. Filip Soudský, Ph.D.
  • Cvičící: RNDr. Filip Soudský, Ph.D.
Literatura
  • CHAKRABORTY, S. Formal Languages and Automata Theory - Regular Expressions and Finite Automata. Zurich, 2003.
  • HOPCROFT, J. F. et al. Introduction to Automata Theory, Languages and Computations. New York, 2001.
  • Nýdl et all. Languages and Automata. 2016.
Vyučovací metody

Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming)

Hodnotící metody

Analýza výkonů studenta, Kombinovaná zkouška

Stáhnout jako PDF