SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Automata and Grammars - NTIN071
Title in English: Automaty a gramatiky
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2019
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/~marta/AG.html
Guarantor: Mgr. Marta Vomlelová, Ph.D.
prof. RNDr. Roman Barták, 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: Friedrich Otto, Dr. (08.02.2018)

The course gives an introduction to automata theory and formal languages. 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 and languages.

Course completion requirements -
Last update: Mgr. Marta Vomlelová, Ph.D. (13.05.2019)

The form of study verification is a credit and an exam. Obtaining credit first is a necessary condition for taking an exam, with the exception of early exam terms. The credit is granted by teachers leading the tutorials based on point evaluation of tests during the semester, possible homeworks, activity etc. The nature of study verification for the credit excludes the possibility of its repetition.

The exam consists of written and oral parts. The written part precedes the oral part. If the written part is evaluated as unsatisfactory, the exam ends as unsatisfactory without taking the oral part. If the oral part is evaluated as unsatisfactory, the student has to repeat both written and oral parts on the next exam term. Final exam grade is based on evaluation of both written and oral parts.

The written part consist of three problem sets. Examples of the written part from previous years are available on the course webpage.

Demands at oral part correspond to the syllabus of the course in the extend that has been presented on lectures.

Literature -
Last update: Mgr. Marta Vomlelová, Ph.D. (18.02.2019)

J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

P.J. Denning, J.E. Dennis, J.E. Qualitz: Machines, Languages, and Computation, Prentice-Hall, 1978

M. Harrison: Introduction to Formal Language Theory, Addison-Wesley, 1978

H.R. Lewis, Ch.H. Papadimitriou: Elements of the Theory of Computation, Prentice-Hall, 1981

G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Language Theory, Vol.1: Word, Language, Grammar, Springer, 1997

Teaching methods -
Last update: Friedrich Otto, Dr. (08.02.2018)

Lectures and exercises

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

Credits from exercises are a necessary condition to attend the final exam.

The final exam consists from a written part and an oral part. Both written and oral part test the acquired understanding of the definitions, theorems, and algorithms presented during the course.

A successful completion of the written part of the final exam is necessary to be admitted to the oral part. The oral exam consists of a deeper analysis of a topic covered by the syllabus to the extend presented during the course.

Syllabus -
Last update: Mgr. Marta Vomlelová, Ph.D. (13.05.2019)

Word, language, operations on languages

Formal grammar, regular grammar, finite-state automaton, Nerode's Theorem, minimal automaton, non-determinism

Closure properties of the class of regular languages, regular expressions, Kleene's Theorem, Pumping Lemma for regular languages

Finite-state transducer, decision problems for regular languages

Context-free grammar, Chomsky normal form, Greibach normal form, closure properties of the class of context-free languages, Pumping Lemma for context-free languages

Pushdown automaton, CYK-algorithm, deterministic pushdown automaton, decision problems for context-free languages

Context-sensitive grammar, context-sensitive language, closure properties and decision problems, linear-bounded automaton

Turing machines, halting problem, reduction, undecidable problems, recursively enumerable language, Chomsky hierarchy

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