SubjectsSubjects(version: 928)
Course, academic year 2022/2023
   Login via CAS
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
Virtual mobility / capacity: no
State of the course: cancelled
Language: Czech
Teaching methods: full-time
Additional information:
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 -
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 (, 1996

R. Barták: Automaty a gramatiky: on-line, elektronický text (, 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.

Charles University | Information system of Charles University |