Languages, automata and grammars
Code  Completion  Credits  Range  Language 

AE4B01JAG  Z,ZK  6  2+2 
 Enrollement in the course requires an assessment of the following courses:
 Discrete mathematics (AE4B01DMA)
 Lecturer:
 Tutor:
 Supervisor:
 Department of Mathematics
 Synopsis:

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, contextfree grammars will be emphasized. The relation will be shown between contextfree grammars and push down automata. Next topic is a Turing machine and the existence of nondecidable problems.
 Requirements:

Discrete Mathematics
 Syllabus of lectures:

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, contextfree grammars.
9.Push down automata and their relation to contextfree languages.
10.Properties of contextfree languages, Pumping Lemma for contextfree languages.
11.Algorithms for some problems concerning contextfree languages.
12.Turing machines.
13.Nondecidable problems.
 Syllabus of tutorials:

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, contextfree grammars.
9.Push down automata and their relation to contextfree languages.
10.Properties of contextfree languages, Pumping Lemma for contextfree languages.
11.Algorithms for some problems concerning contextfree languages.
12.Turing machines.
13.Nondecidable problems.
 Study Objective:
 Study materials:

[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second Edition, AddisonWesley, 2001
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Cybernetics and Robotics  Robotics (elective course)
 Cybernetics and Robotics  Senzors and Instrumention (elective course)
 Cybernetics and Robotics  Systems and Control (elective course)
 Electrical Engineering, Power Engineering and Management  Applied Electrical Engineering (elective course)
 Electrical Engineering, Power Engineering and Management  Electrical Engineering and Management (elective course)
 Communications, Multimedia and Electronics  Communication Technology (elective course)
 Communications, Multimedia and Electronics  Multimedia Technology (elective course)
 Communications, Multimedia and Electronics  Applied Electronics (elective course)
 Communications, Multimedia and Electronics  Network and Information Technology (elective course)
 Open Informatics  Computer Systems (compulsory course in the program)
 Open Informatics  Computer and Information Science (compulsory course in the program)
 Open Informatics  Software Systems (compulsory course in the program)
 Electrical Engineering, Power Engineering and Management (elective course)
 Communications, Multimedia and Electronics (elective course)
 Cybernetics and Robotics (elective course)
 Open Informatics (compulsory course in the program)
 Communications, Multimedia and Electronics  Communications and Electronics (elective course)