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ů.

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.

Pro zı́skánı́ zápočtu je potřeba dostatek bodů ze zápočtových testů. Zkouška se skládá z povinné pı́semné a povinné ústnı́ části.

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.

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.

1. Motivace pro studium formálních jazyků. Základní pojmy (jazyk, abeceda, gramatika, automat), Chomského hierarchie.

2. Deterministické a nedeterministické konečné automaty (DKA a NKA), NKA s epsilon přechody.

3. Operace s automaty (převod na NKA bez epsilon přechodů, na DKA, minimalizace), průnik, sjednocení.

4. Programová realizace DKA a NKA, obvodová realizace.

5. Rozšíření o překlad, Mealey, Moore, převody.

6. Operace s regulárními gramatikami, převody na KA.

7. Regulární výrazy, převody mezi regulárními výrazy, konečnými automaty a regulárními gramatikami, Kleenova věta.

8. Principy využití regulárních výrazů v UNIXu (grep, egrep, perl, PHP, ...).

9. Konečný automat jako lexikální analyzátor, lex/flex generátory.

10. Vlastnosti regulárních jazyků (pumping lemma, Nerodova věta).

11. Jazyky bezkontextové, zasobníkový automat.

12. Analýza bezkontextových jazyků (nedeterministická versus deterministická).

13. Jazyky kontextové a neomezené, Turingův stroj.

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.

5. Adding translation, Mealey, Moore, conversions.

6. Operations on regular grammars, conversions to FA.

7. Regular expressions, regular expression conversions, finite automata and regular grammars, Kleene theorem.

8. Principles of use of regular expressions in UNIX (grep, egrep, perl, PHP, ...).

9. Finite automaton as a lexical analyzer, lex/flex generators.

10. Properties of regular languages (pumping lemma, Nerode theorem).

11. Context-free languages, pushdown automaton.

12. Parsing of context-free languages (nondeterministic versus deterministic).

13. Context-sensitive and recursively enumerable languages, Turing machine.

https://edux.fit.cvut.cz/courses/BI-AAG/

(nutné přihlášení)

https://edux.fit.cvut.cz/courses/BI-AAG/

(login necessary)

Znalosti základních datových struktur a základů programování.

Knowledge of basic data structures and computer programming.