|
Lecturer(s)
|
-
Lhotka Ladislav, Ing. CSc.
-
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
Students receive points during the semester, up to the maximum of 100 points with the following structure: * Exam 55 points (minimum 25) * Practicals 45 points (minimum 25), divided as follows: - test 1 (15 points) - test 2 (15 points) - homework and individual exercises (15 points) In case of reaching at least the minimum amount of points from both exam and practicals, the resulting mark is determined according to the following table: | points | 90-100 | 80-89 | 70-79 | 60-69 | 50-59 | < 50 | | mark | 1 | 1- | 2 | 2- | 3 | 4 | Up to 2 unexcused absences in practicals are tolerated. Tests in regular terms may be done separately only after presenting evidence of a serious reason (such as illness confirmed by a physician, or another reason approved by the teacher in advance). A student may, on his or her own request, retry at most one test (chosen at his or her discretion), in a term set by the teacher. The result of the regular test is hereby completely replaced by the result of the corrective test. The exam is in written form, an oral part is optional (e.g. for explaining parts of the exam test that are unclear). In order to successfully pass the tests and exam, students need to know the contents of lectures, practicals and further educative materials provided on course's web pages (https://elearning.jcu.cz).
|
|
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.
|