Subject description - B4B01JAG
Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
of deterministic languages, and the class of prefix-free languages.
of deterministic languages, and the class of prefix-free languages.
of deterministic languages, and the class of prefix-free languages.
| B4B01JAG | Languages, Automats and Gramatics | ||
|---|---|---|---|
| Roles: | PO, PV, PZ | Extent of teaching: | 2P+2S |
| Department: | 13101 | Language of teaching: | CS |
| Guarantors: | Demlová M. | Completion: | Z,ZK |
| Lecturers: | Demlová M. | Credits: | 6 |
| Tutors: | Demel J., Demlová M. | Semester: | Z |
Web page:
https://moodle.fel.cvut.cz/courses/B4B01JAGAnotation:
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.Study targets:
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.Content:
| 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 |
| 12. | A brief introduction to Turing machines. |
Course outlines:
| 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 |
| 12. | A brief introduction to Turing machines. |
Exercises outline:
| 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 |
| 12. | A brief introduction to Turing machines. |
Literature:
| [1] | J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006. |
Requirements:
NoneKeywords:
Finite automata (deterministic and non deterministic), grammars, context free grammars, pushdown automata. Subject is included into these academic programs:| Program | Branch | Role | Recommended semester |
| BPOI3_2018 | Software | PZ | 3 |
| BPOI1_2018 | Artificial Intelligence and Computer Science | PZ | 5 |
| BPOI3_2016 | Software | PO | 5 |
| MPBIO1_2018 | Bioinformatics | PV | – |
| BPOI1_2016 | Computer and Information Science | PO | 5 |
| BPOI_BO_2016 | Common courses | PO | 5 |
| Page updated 24.4.2024 07:56:49, semester: Z,L/2023-4, Z/2024-5, Send comments about the content to the Administrators of the Academic Programs | Proposal and Realization: I. Halaška (K336), J. Novák (K336) |