Students are introduced to basic theoretical and implementation principles of the following topics: construction, use and mutual transformations of finite automata, regular expressions and regular grammars, translation finite automata, construction and use of pushdown automata, hierarchy of formal languages, Relationships between formal languages and automata. Knowledge acquired through the module is applicable in designs of algorithms for searching in text, data compression, simple parsing and translation, and design of digital circuits.
Last update: Kubová Petra Ing. (02.01.2018)
Studenti získají základní teoretické a implementační znalosti o konstrukci, použití a vzájemných transformací konečných automatů, regulárních výrazů a regulárních gramatik, o překladových konečných automatech a o konstrukci a použití zásobníkových automatů. Znají hierarchii formálních jazyků a rozumějí vztahům mezi formálními jazyky a automaty. Znalosti z teorie automatů umějí aplikovat pro řešení praktických problémů z oblasti vyhledávání v textu, kompresi dat, jednoduchých překladů a návrhu číslicových obvodů.
Aim of the course -
Last update: Kubová Petra Ing. (02.01.2018)
Students will be able to:
Understand finite automata, regular expressions, grammars, and translation finite automata, with an emphasis on their practical use.
Understand the class of context-free languages, basic use of pushdown automata, as well as the classification of languages.
Last update: Kubová Petra Ing. (02.01.2018)
Studenti budou umět:
budou mít základní teoretické a implementační znalosti o konstrukci, použití a vzájemných transformací konečných automatů, regulárních výrazů a regulárních gramatik, o překladových konečných automatech a o konstrukci a použití zásobníkových automatů.
budou znát hierarchii formálních jazyků a rozumějí vztahům mezi formálními jazyky a automaty.
aplikovat znalosti z teorie automatů pro řešení praktických problémů z oblasti vyhledávání v textu, kompresi dat, jednoduchých překladů a návrhu číslicových obvodů.
Literature -
Last update: Kubová Petra Ing. (02.01.2018)
R:Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. "Compilers: Principles, Techniques, and Tools" (2nd Edition). Addison Wesley, 2007. ISBN 0321486811.
R:Kozen, D. C. "Automata and Computability". Springer, 1997. ISBN 0387949070.
R:Melichar, B., Holub, J., Mužátko, P. "Languages and Translations". Praha: Publishing House of CTU, 1997. ISBN 80-01-01692-7.
Last update: Kubová Petra Ing. (02.01.2018)
Z:Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. "Compilers: Principles, Techniques, and Tools" (2nd Edition). Addison Wesley, 2007. ISBN 0321486811.
Z:Kozen, D. C. "Automata and Computability". Springer, 1997. ISBN 0387949070.
Z:Melichar, B., Holub, J., Mužátko, P. "Languages and Translations". Praha: Publishing House of CTU, 1997. ISBN 80-01-01692-7.
Learning resources -
Last update: Kubová Petra Ing. (02.01.2018)
https://edux.fit.cvut.cz/courses/BI-AAG/
(login necessary)
Last update: Kubová Petra Ing. (02.01.2018)
https://edux.fit.cvut.cz/courses/BI-AAG/
(nutné přihlášení)
Syllabus -
Last update: Kubová Petra Ing. (02.01.2018)
1. Motivation to study formal languages. Basic notions (language, alphabet, grammar, automaton), Chomsky hierarchy.
2. Nondeterministic and deterministic finite automata (NFA, DFA), NFA with epsilon transitions.
3. Operations on automata (transformation to NFA without epsilon transitions, to DFA, minimization), intersection, union.
4. Programming implementations of DFA and NFA, circuit implementations.