CTU FEE Moodle
Languages, automata and grammars
This course is not present in Moodle. You can visit its homepage by clicking the "Course page (outside Moodle)" button on the right (if available).
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
Responsible for the data validity:
Study Information System (KOS)