Automaty a gramatiky - NTIN013

• Anglický název: Automata and Grammars
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2004
• Semestr: letní
• E-Kredity: 8
• Rozsah, examinace: letní s.:3/2, 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í
• Další informace: http://kti.mff.cuni.cz/~bartak/automaty/
• Garant: prof. RNDr. Roman Barták, Ph.D.
• Kategorizace předmětu: Informatika > Teoretická informatika
• Neslučitelnost : NTIN071
• Záměnnost : NTIN071
• Je prerekvizitou pro: NSWI002, NPFL049, NTIN019
• Je záměnnost pro: NUIN002

Anotace

čeština

Poslední úprava: T_KTI (15.05.2003)

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).

angličtina

Poslední úprava: T_KTI (15.05.2003)

Introductory lectures on Automata Theory and Formal Grammars. The emphasis is put on basic terminology and fundamental results. We study and highlight connections between the following formal models: finite-state and push-down automata (both deterministic and non-deterministic), Turing machines (including the halting problem), regular, context-free, and context-sensitive grammars.

Literatura

Poslední úprava: T_KTI (15.05.2003)

M. Chytil: Automaty a gramatiky, SNTL Praha, 1984

V. Koubek: Automaty a gramatiky, elektronický text (http://kti.mff.cuni.cz/downloads/Automstr_ps.zip), 1996

R. Barták: Automaty a gramatiky: on-line, elektronický text (http://kti.mff.cuni.cz/~bartak/automaty/), 2001

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

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

M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL Praha, 1990

J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

Sylabus

čeština

Poslední úprava: T_KTI (15.05.2003)

Konečné automaty a regulární jazyky, Nerodova věta, ekvivalence a redukce automatů, nedeterminismus.

Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, pumping (iterační) lemma.

Gramatiky, Chomského hierarchie, regulární, bezkontextové a kontextové gramatiky

Bezkontextové gramatiky, derivace, redukce, normální tvary, pumping (iterační) lemma, uzávěrové vlastnosti, deterministické a nedeterministické zásobníkové automaty.

Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy

angličtina

Poslední úprava: T_KTI (15.05.2003)

Finite-state automata and regular languages, Nerode theorem, equivalence and reduction of automata, non-determinism.

Closure properties, regular expressions, Kleene theorem, pumping lemma.

Formal grammars, Chomsky hierarchy, regular, context-free, and context-sensitive grammars.

Context-free grammars, derivation, reduction, normal forms, pumping lemma, closure properties, deterministic and non-deterministic push-down automata.

Recursively enumerable languages, Turing machines, algorithmically undecidable problems.