Oct 23, 2020   11:28 a.m. Alojza
Academic information system

Course syllabus I-AFJ - Automata and formal languages (FEEIT - SS 2019/2020)

     Information sheet          ECTS          Syllabus          

     Slovak          English          

University: Slovak University of Technology in Bratislava
Faculty of Electrical Engineering and Information Technology
Course unit code:
Course unit title:
Automata and formal languages
Mode of delivery, planned learning activities and teaching methods:
2 hours weekly (on-site method)
2 hours weekly (on-site method)

Credits allocated:
Recommended semester/trimester: Applied Informatics - master (compulsory), 2. semester
Level of study:
Prerequisites for registration:
Assesment methods:
There are four programming assignments worth 10 pts each. For grade A student needs to have at least 92 points, grade B at least 83 points, grade C at least 74 points, grade D at least 65 points and grade E at least 56 points. Student with less than 20 points from the programming assignments will not be given the credit.
Learning outcomes of the course unit:
The goal of the course is to provide to students an extended knowledge of formal languages, finite automata, pushdown automata and their usage in compilers and the compilation of source code into a different source code (or assembly language / machine code). After completing the course, the students will understand the lexical and syntactic analyses of computer programmes.
Course contents:
1. Languages and their representation, grammars.
2. Finite automata and regular languages. NFA, DFA, their equivalency. Minimization of DFA. Pumping lemma for regular languages.
3. Context-free grammars and their transformations. Chomsky Normal Form. Pumping lemma for context-free languages. Pushdown automata.
4. Compilator's structure. Lexical analysis. FLEX.
5. Syntactic analysis (parsing). CYK algorithm.
6. Top-down syntactic analysis. LL(1) analyzer.
7. Bottom-up syntactic analysis. LR(0) analyzer, SLR(1) analyzer, LR(1) analyzer, LALR(1) analyzer.
8. Conflicts at syntactic analysis. GLR analyzer.
Recommended or required reading:
HOPCROFT, J E. -- ULLMAN, J D. Formálne jazyky a automaty. Bratislava : Alfa, 1978. 342 p.
DEDERA, Ľ. Počítačové jazyky a ich spracovanie. Liptovský Mikuláš : Akadémia ozbrojených síl generála M.R. Štefánika, 2014. 277 p. ISBN 978-80-8040-503-8.
LINZ, P. An Introduction to Formal Languages and Automata. Sudbury : Jones and Bartlett Publ.,Inc, 2006. 415 p. ISBN 978-0-7637-3798-6.

Language of instruction:
slovak or english
Courses evaluation:
Assessed students in total: 597

13,4 %
9,0 %
17,1 %
18,8 %
30,3 %
11,4 %
Name of lecturer(s): prof. RNDr. Otokar Grošek, PhD. (person responsible for course) - slovak, english
Ing. Viliam Hromada, PhD. (examiner, instructor, lecturer, tutor) - slovak, english
Last modification:
9. 5. 2019
prof. RNDr. Otokar Grošek, PhD. and programme supervisor

Last modification made by RNDr. Marian Puškár on 05/09/2019.

Type of output: