SubjectsSubjects(version: 821)
Course, academic year 2017/2018
   Login via CAS
Automata and Grammars - NTIN071
English title: Automaty a gramatiky
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017 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: https://dl1.cuni.cz/course/view.php?id=5119
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: 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: Friedrich Otto, Dr. (08.02.2018)

A) The Seminary

The seminary will take place weekly on Thursdays from 10:40 to 12:10.

In an accompanying Moodle course there will be weekly assignments published.

Assignments:

The students should solve the problems from the assignments and be prepared to present their solutionsin the seminary. In each meeting of the seminary several students will be asked to present some oftheir solutions at the blackboard. Each student is expected to do this at least twice in the course of the term.

The students get points for their presentations. These points will account for 10 % of the final grade of the course.

Midterm:

There will be a one-hour written exam on Thursday, April 5. The points obtained in this exam will account for another 20 % of the final grade of the course.

To pass the seminary, two successful presentations in class and participation in the midterm are required.

Continuous work throughout the whole term is required to obtain the credits for the seminary. Therefore, there will be no additional possibility to acquire them later.

B) The Lecture

The lecture will be given on Thursdays from 9:00 to 10:30.

There will be a written exam at the end of the term, probably on May 31 (and a second one on June 14 for those students who missed the first one or failed it). This exam accounts for 50 % of the final grade.

Finally, there will be an oral exam, probably on June 14 (and a second one on June 28 for those students who missed the first one or failed it). The oral exam can only be taken after the written exam has been taken. It accounts for the final 20 % of the final grade.

The following table gives the final grade according to the score achieved from the presentations in the seminary, the midterm, the written final exam, and the oral exam:

grade 1 grade 2 grade 3 failure
100%–85% 84%–71% 70%–55% less than 55%

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

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

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

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

Credits from exercises obtained by presenting solutions in the seminary are a necessary condition to attend the final exam.

Another requirement is participation in the midterm, which consists of a written test of one hour.

The final exam consists from a written part and an oral part. The written test lasts two hours. The students are given six problems that they are expected to solve. These problems 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: Friedrich Otto, Dr. (08.02.2018)

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, CKY-algorithm, deterministic pushdown automaton, decision problems for context-free languages

Context-sensitive grammar, context-sensitive language, Kuroda normal form, 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