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). Other 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)
prof. 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)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor), prof. RNDr. Ivana Černá, CSc. (deputy)
Guaranteed by
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 Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
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. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. 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)
Během semestru jedna pisemná zkouška. Závěrečná zkouška je rovněž písemná; obě bez použití materiálů.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Autumn 1999, Autumn 2000.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2001/I006