Go to menu

Information System of Masaryk University

Course Information

česky | in English

I006 Formal Languages and Automata II

Faculty of Informatics
Autumn 2001

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Alternate Types of Completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer), prof. RNDr. Ivana Černá, CSc. (deputy)
prof. RNDr. Ivana Černá, CSc. (seminar tutor)
doc. RNDr. Jiří Barnat, Ph.D. (seminar tutor), prof. RNDr. Ivana Černá, CSc. (deputy)
RNDr. Jaroslav Ráček, Ph.D. (seminar tutor), prof. RNDr. Ivana Černá, CSc. (deputy)
RNDr. Vojtěch Řehák, Ph.D. (seminar tutor), prof. RNDr. Ivana Černá, CSc. (deputy)

Supervisor

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science - Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 15:00–17:50 D1

Timetable of Seminar Groups:

I006/02 each even Thursday 9:00–10:50 B007, J. Barnat
I006/06 each even Thursday 9:00–10:50 B003, V. Řehák
I006/01 each odd Thursday 9:00–10:50 B007, J. Barnat
I006/05 each odd Thursday 9:00–10:50 B003, V. Řehák
I006/04 each even Thursday 15:00–16:50 B007, J. Barnat
I006/08 each even Thursday 15:00–16:50 B011, V. Řehák
I006/03 each odd Thursday 15:00–16:50 B007, J. Barnat
I006/07 each odd Thursday 15:00–16:50 B011, V. Řehák

Prerequisites (in Czech)

I005 Formal Languages and Automata I || I505 Formal Languages and Automata I

Course Enrollment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

Fields of study the course is directly associated with

Informatics (programme FI, B-IN)
Information Technology (programme FI, B-IN)
Informatics (programme FI, M-IN)
Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)

Course objectives (in Czech)

Deterministické bezkontextové jazyky (detCFL) a jejich syntaktická analýza.
SLL(k) a LL(k) gramatiky a jazyky; vlastnosti a analyzátory.
LR(k), SLR(k) a LALR(k) gramatiky a jazyky; vlastnosti a analyzátory.
Vztahy mezi LL, LR a detCFL.
(Ne)rozhodnutelné problémy z oblasti detCFL.
Specifikace přechodových systémů; bisimulace; vybrané (ne)rozhodnutelné problémy se vztahem k verifikaci procesů.
Další typy automatů a jejich aplikace. (automaty s výstupem, automaty pracujici nad nekonecnymi slovy, stromové automaty,...)

Syllabus

Deterministic context-free languages (detCFL).
Methods of syntactic analyses of detCFLs.
SLL(k) and LL(k) grammars and languages, properties and analyzers.
LR(k), SLR(k) and LALR(k) grammars and languages, properties and analyzers.
Relationships between LL, LR and detCFL.
Automata as an intance of transition systems; bisimulation, concurrent processes - their families and relationships (Un)decidable problems w.r.t. bisimulation.
Other types of automata and their applications (automata with output, automata on infinite strings, tree automata).

Literature

AHO, Alfred V., Ravi SETHI and Jeffrey D. ULLMAN. Compilers, principles, techniques, and tools. Reading: Addison-Wesley Publishing Company, 1987. x, 796 s. ISBN 0-201-10088-6. info
CHYTIL, Michal. Automaty a gramatiky. 1. vyd. Praha: SNTL - Nakladatelství technické literatury, 1984. 331 s. info
KOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0-387-94907-0. info
SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990. 417 s. ISBN 0-387-51732-4. info

Assessment methods (in Czech)