VSFS:N_AG Automata and Grammars - Course Information
N_AG Automata and Grammars
University of Finance and AdministrationWinter 2025
- Extent and Intensity
- 2/1/0. 6 credit(s). Type of Completion: zk (examination).
- Guaranteed by
- prof. RNDr. Ondřej Čepek, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ivana Plačková - Prerequisites
- There are no prerequisites for this course.
- Course Enrolment Limitations
- The course is offered to students of any study field.
- Course objectives
- The aim of the subject is to acquaint students with the concept of finite automata (deterministic and nondeterministic) and regular languages. The equivalence with regular grammars and regular expressions will also be studied.
- Learning outcomes
- Na konci tohoto kurzu bude student schopen navrhovat konečné automaty (deterministické i nedeterministické) pro konkrétní jazyky. Bude schopen porozumět regulárnímu výrazu a také regulární výraz popisující konkrétní jazyk vytvořit. Dále bude umět přepsat konečný automat do systému pravidel, tedy do regulární gramatiky.
- Syllabus
- 1. Deterministické konečné automaty (DFA) a regulární jazyky (REG) 2. Pumping lemma a jeho použití, Myhill-Nerodova věta a příklady neregulárních jazyků 3. Nedeterministické KA (NFA) a jejich ekvivalence s DFA 4. Regulární výrazy a Kleeneho věta 5. Regulární gramatiky 6. Algoritmy založené na DFA (Aho-Corasick a Knuth-Morris-Pratt)
- Literature
- recommended literature
- Eliška Šestáková: Automaty a Gramatiky – Sbírka řešených příkladů (nakladatelství ČVUT 2020)
- M. Chytil: Automaty a gramatiky, Praha, SNTL, 1984
- Teaching methods
- Theory explanation, problem solving.
- Assessment methods
- The course ends with a written examination. Duration 60 minutes.
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
- Enrolment Statistics (recent)
- Permalink: https://is.vsfs.cz/course/vsfs/winter2025/N_AG