I006 Formal Languages and Automata II

Faculty of Informatics
Autumn 1999
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)
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
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.
  • Selected applications(compilers, concurrent processes - bisimulation).
  • (Un)decidable problems for automata and grammars w.r.t. bisimulation.
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, při níž je povoleno použití vlastních materiálů (knihy, poznámky z přednášek, cvičení atp.). Závěrečná zkouška je rovněž písemná, a to 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 2000, Autumn 2001.
  • Enrolment Statistics (Autumn 1999, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn1999/I006