SubjectsSubjects(version: 853)
Course, academic year 2019/2020
  
Automata and Grammars - B500005
Title: Automaty a gramatiky
Guaranteed by: CTU in Prague, Faculty of Information Technology (500)
Actual: from 2019
Semester: winter
Points: winter s.:6
E-Credits: winter s.:6
Examination process: winter s.:
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unknown / unknown (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
Level:  
For type: Bachelor's
Guarantor: Holub Jan prof. Ing. Ph.D.
Janoušek Jan doc. Ing. Ph.D.
Interchangeability : N500009
Annotation -
Last update: Kubová Petra Ing. (02.01.2018)
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.
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.

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.

Learning resources -
Last update: Kubová Petra Ing. (02.01.2018)

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

(login necessary)

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.

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.

Registration requirements -
Last update: Kubová Petra Ing. (02.01.2018)

Knowledge of basic data structures and computer programming.

Course completion requirements - Czech
Last update: Svozil Daniel doc. Mgr. Ph.D. (07.02.2018)

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.

Teaching methods
Activity Credits Hours
Účast na přednáškách 1 28
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi 1 28
Práce na individuálním projektu 2 56
Příprava na zkoušku a její absolvování 1 28
Účast na seminářích 1 28
6 / 6 168 / 168
Coursework assessment
Form Significance
Examination test 30
Continuous assessment of study performance and course -credit tests 40
Oral examination 30

 
VŠCHT Praha