Jazyky a automaty

Zkratka předmětu KMI/JA
Název předmětu Jazyky a automaty
Akademický rok 2019/2020
Pracoviště / Zkratka KMI/JA
Název Jazyky a automaty
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 2 HOD/TYD Cvičení 2 HOD/TYD
Vyučovací jazyk čeština
Nahrazovaný předmět
Vyloučené předměty KMI/LA, KMI/YLA
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
  • DEMLOVÁ, M. a V. KOUBEK. Algebraická teorie automatů. Praha, 1990.
  • http://www.fi.muni.cz/usr/kretinsky/afj_I.ps
  • CHYTIL,M. Automaty a gramatiky. Praha, 1984.
  • 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 a kol. Jazyky a automaty. 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