Information sheet ECTS Syllabus
Course syllabus I-AFJ - Automata and formal languages (FEEIT - SS 2019/2020)
|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:|
|Recommended semester/trimester:||Applied Informatics - master (compulsory), 2. semester|
Level of study:
|Prerequisites for registration:|
|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.
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:
Language of instruction:
|slovak or english|
|Assessed students in total: 597|
|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
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.