Languages and Automata

Zkratka předmětu KMI/YLA
Název předmětu Languages and Automata
Akademický rok 2019/2020
Pracoviště / Zkratka KMI/YLA
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 KMI/LA
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 zápočtové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 al. 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