Languages and Automata

Zkratka předmětu KMI/LA
Název předmětu Languages and Automata
Akademický rok 2020/2021
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. Mgr. Ing. Petr Klán, CSc.
  • Přednášející: doc. Mgr. Ing. Petr Klán, CSc.
  • Cvičící: doc. Mgr. Ing. Petr Klán, CSc.
Literatura
  • CHAKRABORTY, S. Formal Languages and Automata Theory - Regular Expressions and Finite Automata. Zurich, 2003.
  • Nýdl et all. Languages and Automata. 2016.
  • HOPCROFT, J. F. et al. Introduction to Automata Theory, Languages and Computations. New York, 2001.
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