N_AG Automata and Grammars

University of Finance and Administration
Winter 2024
Extent and Intensity
2/1/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ondřej Čepek, Ph.D. (seminar tutor)
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á
Timetable of Seminar Groups
N_AG/vIPH: Fri 10. 1. 14:00–15:30 E305, 15:45–17:15 E305, 17:30–19:00 E305, Fri 17. 1. 14:00–15:30 E305, 15:45–17:15 E305, 17:30–19:00 E305, O. Čepek
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.
The course is also listed under the following terms Winter 2014, Winter 2015, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023, Winter 2025.
  • Enrolment Statistics (Winter 2024, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/winter2024/N_AG