SubjectsSubjects(version: 802)
Course, academic year 2016/2017
   Login via CAS
Automata and Grammars - NTIN071
Czech title: Automaty a gramatiky
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2016
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://ktiml.mff.cuni.cz/~bartak/automaty/
Guarantor: prof. RNDr. Roman Barták, Ph.D.
doc. RNDr. Pavel Surynek, Ph.D.
Mgr. Marta Vomlelová, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Is pre-requisite for: NTIN046
Annotation -
Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

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.
Aim of the course -
Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

The course gives introduction information about automata theory adnd formal grammars. The students will learn the following formal models and their basic properties: finite-state and push-down automata (both deterministic and non-deterministic), Turing machines (including the halting problem), regular, context-free, and context-sensitive grammars.

Literature -
Last update: prof. RNDr. Roman Barták, Ph.D. (16.02.2017)

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

V. Koubek: Automaty a gramatiky, elektronický text (http://ktiml.mff.cuni.cz/ktiml/teaching/files/materials/Automstr_ps.zip), 1996

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

Teaching methods -
Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

lecture and exercises

Syllabus -
Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html