CTU FEE Moodle
Languages, Automats and Gramatics
B232 - Summer 23/24
This is a grouped Moodle course. It consists of several separate courses that share learning materials, assignments, tests etc. Below you can see information about the individual courses that make up this Moodle course.
Languages, Automats and Gramatics - B4B01JAG
Main course
| Credits | 6 |
| Semesters | Winter |
| Completion | Assessment + Examination |
| Language of teaching | Czech |
| Extent of teaching | 2P+2S |
Annotation
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.
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.
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 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.
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
Languages, automata and grammars - A4B01JAG
| Credits | 6 |
| Semesters | Winter |
| Completion | Assessment + Examination |
| Language of teaching | Czech |
| Extent of teaching | 2+2 |
Annotation
The course covers basics of the theory of finite automata and grammars: deterministic and nondeterministic finite automata, characterization of the class of languages accepting by a finite automaton and description of such a language by a regular expression. Grammars and languages generated by a grammar, context-free grammars will be emphasized. The relation will be shown between context-free grammars and push down automata. Next topic is a Turing machine and the existence of non-decidable problems.
Study targets
No data.
Course outlines
1. Alphabet, strings over an alphabet, concatenation of words, language.
2. Deterministic finite automaton, state diagram.
3. Language accepted by a finite automaton, Nerode?s Theorem.
4. Nondeterministic finite automata.
5. Equivalence of deterministic and nondeterministic finite automata.
6. Regular expressions and regular languages, Kleen?s Theorem.
7. Properties of regular languages.
8. Grammars, regular grammars, context-free grammars.
9. Push down automata and their relation to context-free languages.
10. Properties of context-free languages, Pumping Lemma for context-free languages.
11. Algorithms for some problems concerning context-free languages.
12. Turing machines.
13. Non-decidable problems.
2. Deterministic finite automaton, state diagram.
3. Language accepted by a finite automaton, Nerode?s Theorem.
4. Nondeterministic finite automata.
5. Equivalence of deterministic and nondeterministic finite automata.
6. Regular expressions and regular languages, Kleen?s Theorem.
7. Properties of regular languages.
8. Grammars, regular grammars, context-free grammars.
9. Push down automata and their relation to context-free languages.
10. Properties of context-free languages, Pumping Lemma for context-free languages.
11. Algorithms for some problems concerning context-free languages.
12. Turing machines.
13. Non-decidable problems.
Exercises outlines
1. Alphabet, strings over an alphabet, concatenation of words, language.
2. Deterministic finite automaton, state diagram.
3. Language accepted by a finite automaton, Nerode?s Theorem.
4. Nondeterministic finite automata.
5. Equivalence of deterministic and nondeterministic finite automata.
6. Regular expressions and regular languages, Kleen?s Theorem.
7. Properties of regular languages.
8. Grammars, regular grammars, context-free grammars.
9. Push down automata and their relation to context-free languages.
10. Properties of context-free languages, Pumping Lemma for context-free languages.
11. Algorithms for some problems concerning context-free languages.
12. Turing machines.
13. Non-decidable problems.
2. Deterministic finite automaton, state diagram.
3. Language accepted by a finite automaton, Nerode?s Theorem.
4. Nondeterministic finite automata.
5. Equivalence of deterministic and nondeterministic finite automata.
6. Regular expressions and regular languages, Kleen?s Theorem.
7. Properties of regular languages.
8. Grammars, regular grammars, context-free grammars.
9. Push down automata and their relation to context-free languages.
10. Properties of context-free languages, Pumping Lemma for context-free languages.
11. Algorithms for some problems concerning context-free languages.
12. Turing machines.
13. Non-decidable problems.
Literature
[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001
Requirements
Discrete Mathematics