I006 Formal Languages and Automata II

Faculty of Informatics
Autumn 2000
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.
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
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
  • HOPCROFT, John E. and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979, 418 s., ob. ISBN 0-201-02988-X. 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 1 : languages and parsing. Berlin: Springer-Verlag, 1988, 228 s. ISBN 0-387-13720-3. 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.
The course is taught: every week.
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 2001.
  • Enrolment Statistics (Autumn 2000, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2000/I006