VSFS:N_AG Automata and Grammars - Course Information

N_AG Automata and Grammars

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