Subject description - B4B01JAG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
B4B01JAG Languages, Automats and Gramatics Extent of teaching:2P+2S
Guarantors:Demlová M. Roles:PO,PZ Language of
teaching:
CS
Teachers:Demlová M. Completion:Z,ZK
Responsible Department:13101 Credits:6 Semester:Z

Anotation:

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
of deterministic languages, and the class of prefix-free languages.
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
of deterministic languages, and the class of prefix-free languages.
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
of deterministic languages, and the class of prefix-free languages.
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:

None

Webpage:

https://math.feld.cvut.cz/demlova/teaching/jag_vyuka.html

Keywords:

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
BPOI3_2016 Software PO 5
BPOI1_2018 Artificial Intelligence and Computer Science PZ 5
BPOI1_2016 Computer and Information Science PO 5
BPOI_BO_2016 Common courses PO 5


Page updated 6.12.2019 17:52:32, semester: Z,L/2020-1, L/2018-9, Z,L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)