|
Lecturer(s)
|
-
Skrbek Miroslav, Ing. Ph.D.
|
|
Course content
|
Content of lectures: 1. Discrete mathematics - necessary prerequisites 2. Symbols, strings, languages 3. Regular languages: regular expressions, finite automata and regular grammars 4. Properties of regular languages, pumping lemma 5. Context-free gramamrs and languages 6. Parsing: derivation tree, algorithms, LL grammars 7. Simplification of context-free grammars, Chomsky and Greibach normal forms 8. Push-down automata 9. Properties of context-free grammars 10. Turing machine 11. Turing hypothesis and the notion of algorithm 12. Modifications of the Turing machine, universal Turing machine 13. LInear bounded automaton 14. Recursively enumerable languages, Chomsky hierarchy 15. Limits of algorithmic computation, the problem of halting the Turing machine Content of practicals: Practicals will extend and complement lecture topics with practical problems with an emphasis on syntactic analysis.
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing)
- Class attendance
- 56 hours per semester
- Preparation for classes
- 56 hours per semester
- Preparation for exam
- 38 hours per semester
|
|
Learning outcomes
|
The course deals with the theory of formal languages and automata, with emphasis on syntactic analysis.
Students will gain essential insight into the theory of formal languages, and a more detailed knowledge about regular and context-free languages. This will help them with designing simple languages and selecting appropriate software tools.
|
|
Prerequisites
|
Basic knowledge of discrete matematics (sets, functions, graphs, trees)
|
|
Assessment methods and criteria
|
Written examination, Interim evaluation
Each student may take 100 points (55 points for examination, 45 points for seminars). The minimum for seminars for evaluation of continuous work is 25 points, including tests that cannot be repeated. To pass the course, the point limit for seminars must be reached, the total number of points (examination and seminars) must be greater or equal to 50, and the examination must be evaluated to 25 points or more. If any of these conditions is not satisfied, the student fails. Detailed information about the points from the continuous evaluation in seminars is announced on the platform E-learning on the course pages for the given year.
|
|
Recommended literature
|
-
Chytil, M. Automaty a gramatiky. Praha: SNTL, 1984.
-
Linz, P. Formal Languages and Automata. Fifth Edition. Sudbury:Jones and Bartlett, 2012. ISBN 978-1-4496-1552-9.
-
Melichar B. et al. Jazyky a překlady: Cvičení. Skriptum FEL ČVUT. Praha: Nakladatelství ČVUT, 2004. ISBN 80-01-03031-8.
-
Melichar, B. Jazyky a překlady. Skriptum FEL ČVUT, 2. vydání. Praha: Nakladatelství ČVUT, 2003. ISBN 80-01-02776-7.
|