Languages, Automats and Gramatics
Code  Completion  Credits  Range  Language 

B4B01JAG  Z,ZK  6  2P+2S  Czech 
 Garant předmětu:
 Marie Demlová
 Lecturer:
 Marie Demlová
 Tutor:
 Jiří Demel, Marie Demlová
 Supervisor:
 Department of Mathematics
 Synopsis:

Basic notions of the theory of finite automata and grammars: deterministic and non deterministic finite automata, languages accepted by finite automata, regular expressions. Grammars and languages generated by grammars with emphasis to context free grammars. A very brief introduction of Turing machines.
 Requirements:

None
 Syllabus of lectures:

1. Alphabet, words over an alphaber, concatenation of words, languages.
2. Deterministic finite automaton. Languages accepted by finite automata  regular languages.
3. Pumping Lemma and Nerode Theorem. Reduced finite automaton
4. Non deterministic finite automata. Subset construction. Properties of the class of regular languages.
5. Regular expressions. Relationship of regular languages and regular expressions. Kleen Theorem
6. Algorithmic approach to problems concering finite automata and regular languages. Introduction of grammars.
7. Chomsky hierarchy of languages generated by grammars. Regular grammars and retular languages. Context free grammars and context free languages.
8. Pumping Lemma for context free languages. Reduced context free grammars.
9. Pushdown automata, two types of languages accepted by pushdown automata.
10. Properties of the class of context free languages.
11. Deterministic pushdown automata and properties of languages accepted by them. The class
of deterministic languages, and the class of prefixfree languages.
12. A brief introduction to Turing machines.
 Syllabus of tutorials:

1. Alphabet, words over an alphaber, concatenation of words, languages.
2. Deterministic finite automaton. Languages accepted by finite automata  regular languages.
3. Pumping Lemma and Nerode Theorem. Reduced finite automaton
4. Non deterministic finite automata. Subset construction. Properties of the class of regular languages.
5. Regular expressions. Relationship of regular languages and regular expressions. Kleen Theorem
6. Algorithmic approach to problems concering finite automata and regular languages. Introduction of grammars.
7. Chomsky hierarchy of languages generated by grammars. Regular grammars and retular languages. Context free grammars and context free languages.
8. Pumping Lemma for context free languages. Reduced context free grammars.
9. Pushdown automata, two types of languages accepted by pushdown automata.
10. Properties of the class of context free languages.
11. Deterministic pushdown automata and properties of languages accepted by them. The class
of deterministic languages, and the class of prefixfree languages.
12. A brief introduction to Turing machines.
 Study Objective:

The aim of the course is to introduce students to the basics of the theory of formal languages. The main tools are finite automata and grammars.
 Study materials:

[1] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd Edition, AddisonWesley, 2006.
 Note:
 Further information:
 https://moodle.fel.cvut.cz/courses/B4B01JAG
 Timetable for winter semester 2024/2025:
 Timetable is not available yet
 Timetable for summer semester 2024/2025:
 Timetable is not available yet
 The course is a part of the following study plans:

 Open Informatics  Computer Science 2016 (compulsory course of the specialization)
 Open Informatics  Software 2016 (compulsory course of the specialization)
 Open Informatics (compulsory course of the specialization)
 Medical electronics and bioinformatics (compulsory elective course)
 Open Informatics  Artificial Intelligence and Computer Science 2018 (compulsory course of the branch)
 Open Informatics  Software 2018 (compulsory course of the branch)