Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Automata and Grammars - NTIN071

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 to 2016
Semester:	summer
E-Credits:	6
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
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 incompatible with:	NTIN013
Is pre-requisite for:	NTIN046
Is interchangeable with:	NUIN002, NTIN013

Opinion survey results Examination dates Schedule Noticeboard

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: Friedrich Otto, Dr. (08.02.2018)

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: Friedrich Otto, Dr. (08.02.2018)

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: Friedrich Otto, Dr. (08.02.2018)

lecture and exercises

Syllabus -

Last update: Friedrich Otto, Dr. (08.02.2018)

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.