Automata Theory - NUIN002

• Title: Teorie automatů
• Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2004
• Semester: winter
• E-Credits: 11
• Hours per week, examination: winter s.:2/2, C [HT]; summer s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Classification: Informatics > Theoretical Computer Science
• Interchangeability : NTIN013, NTIN071

Annotation

English

Last update: T_KSVI (14.04.2003)

A basic course in automata and formal languages theory. The following models are covered: finite state automata, pushdown automata, Turing machines, linear bounded automata, Chomsky hierarchy of grammars and formal languages. The course is taught last time this academic year.

Czech

Last update: T_KSVI (14.04.2003)

Základní přednáška z teorie automatů a formálních jazyků určená pro posluchače učitelského a bakalářského studia informatiky. Probírají se základní modely konečných automatů, zásobníkových automatů, Turingových strojů a lineárně omezených automatů společně s Chomského hierarchií gramatik a formálních jazyků. Upozornění pro studenty: Tento předmět je v tomto akademickém roce vyučován naposledy.

Literature

Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

[1] Chytil,M.: Automaty a gramatiky, SNTL, 1984

[2] Hopcroft,J.E.-Ullman,J.D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Slovenský překlad: Formálne jazyky a automaty, Alfa, Bratislava 1978

[3] Chytil,M.: Teorie automatů a formálních jazyků, skripta MFF UK, 1978

[4] Chytil,M.: Sbírka řešených příkladů z teorie automatů a formálních jazyků, skripta MFF UK, 1978

Syllabus

Last update: G_I (07.05.2002)

1. Konečné automaty
deterministické a nedeterministické konečné automaty, Nerodova věta, redukce konečných automatů, regulární výrazy, Kleeneho veta, regulární jazyky a jejich uzávěrové vlastnosti, sekvenční stroje

2. Chomského hierarchie
regulární, bezkontextové, kontextové jazyky a jazyky typu 0

3. Bezkontextové jazyky
bezkontextové gramatiky, nevypouštějící gramatiky, lineární gramatiky, redukce bezkontextových gramatik, Chomského normální forma, věta o vkládání (tzv. pumping lemma). Zásobníkové automaty, přijímání koncovým stavem a prázdným zásobníkem. Uzávěrové vlastnosti, deterministické jazyky - jejich uzavřenost na doplněk.

4. Principy syntaktické ananlýzy
kanonické odvození, jednoznačné gramatiky a jazyky, princip analýzy shora a zdola, LL(1) a LL(k) gramatiky

5. Turingovy stroje a jazyky typu 0
rozhodnutelné a rozpoznatelné jazyky, Postova veta, univerzální Turingů stroj, algoritmicky nerozhodnutelné problémy (halting problém, Postů korespondenční problém, algoritmicky neřešitelné problémy z teorie jazyků)

6. Lineárně omezené automaty