Teorie automatů - NUIN002

• Anglický název: Automata Theory
• Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2004
• Semestr: zimní
• E-Kredity: 11
• Rozsah, examinace: zimní s.:2/2, Z [HT]; letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Kategorizace předmětu: Informatika > Teoretická informatika
• Záměnnost : NTIN013, NTIN071

Anotace

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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.

Literatura

Poslední úprava: 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

Sylabus

Poslední úprava: 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