Subjects

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

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

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: 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.

Literature - Czech

Last update: 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

Syllabus -

Last update: 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.