SubjectsSubjects(version: 807)
Course, academic year 2017/2018
   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

Requirements to the exam -
Last update: Mgr. Marta Vomlelová, Ph.D. (09.10.2017)

Credit from exercises is a necessary condition to attend the exam.

The exam consists from a witten and an oral part. The written test contains twelve questions corresponding to the syllabus and testing abilities gained on exercises as well as the understanding of definitions, theorems and algotihms presented during the course.

A successfull completition of the witten part is necessary to continue with the oral part. The oral exam consists of a deeper analysis of a topic covered by syllabus in the extend presented during the course.

Failure in the oral part leads to repeatement both witten and oral part of the exam.

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