Aug 19, 2019   9:18 p.m. Lýdia
Academic information system

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


     Information sheet          ECTS          Syllabus          


     Slovak          English          


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

 
Credits allocated: 6
 
Recommended semester/trimester: Applied Informatics - master (compulsory), 2. semester
Level of study: 2.
Prerequisites for registration: none
 
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:
Basic:
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
 
Notes:
 
Courses evaluation:
Assessed students in total: 491

ABCDEFX
13,0 %8,1 %16,7 %18,1 %33,6 %10,5 %
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: 16. 4. 2018
Supervisor: prof. RNDr. Otokar Grošek, PhD. and programme supervisor


Last modification made by RNDr. Marian Puškár on 04/16/2018.

Type of output: