Automata and Grammars - NTIN013

• Title: Automaty a gramatiky
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2004
• Semester: summer
• E-Credits: 8
• Hours per week, examination: summer s.:3/2, 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
• Additional information: http://kti.mff.cuni.cz/~bartak/automaty/
• Guarantor: prof. RNDr. Roman Barták, Ph.D.
• Classification: Informatics > Theoretical Computer Science
• Incompatibility : NTIN071
• Interchangeability : NTIN071
• Is pre-requisite for: NSWI002, NPFL049, NTIN019
• Is interchangeable with: NUIN002

Annotation

English

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.

Last update: T_KTI (15.05.2003)

Czech

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

Last update: T_KTI (15.05.2003)

Literature

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

Last update: T_KTI (15.05.2003)

Syllabus

English

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.

Last update: T_KTI (15.05.2003)

Czech

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

Last update: T_KTI (15.05.2003)