Subject description - AD4B01JAG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
AD4B01JAG Languages, automata and grammars Extent of teaching:14+6
Guarantors:  Roles:P,V Language of
teaching:
CS
Teachers:  Completion:Z,ZK
Responsible Department:13101 Credits:6 Semester:Z

Anotation:

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.

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.

Exercises outline:

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.

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

Subject is included into these academic programs:

Program Branch Role Recommended semester
BKEEM1 Applied Electrical Engineering V 3
BKEEM_BO Common courses V 3
BKEEM2 Electrical Engineering and Management V 3
BKOI1 Computer Systems P 3
BKOI_BO Common courses P 3
BKOI3 Software Systems P 3
BKOI2 Computer and Information Science P 3
BKKYR1 Robotics V 3
BKKYR_BO Common courses V 3
BKKYR3 Systems and Control V 3
BKKYR2 Sensors and Instrumentation V 3
BKKME1 Communication Technology V 3
BKKME_BO Common courses V 3
BKKME4 Network and Information Technology V 3
BKKME3 Applied Electronics V 3
BKKME2 Multimedia Technology V 3
BIS(ECTS)-D Intelligent Systems V 3
BKSTMWM Web and Multimedia V 3
BKSTMSI Software Engineering V 3
BKSTMMI Manager Informatics V 3
BKSTMIS Intelligent Systems V 3
BKSTM_BO Common courses V 3
BSI(ECTS)-D Software Engineering V 3
BWM(ECTS)-D Web and Multimedia V 3
BMI(ECTS)-D Manager Informatics V 3


Page updated 13.12.2019 17:52:09, 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)