I006 Formální jazyky a automaty II

Fakulta informatiky
podzim 1999
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Mojmír Křetínský, CSc. (přednášející), prof. RNDr. Ivana Černá, CSc. (zástupce)
prof. RNDr. Ivana Černá, CSc. (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Mojmír Křetínský, CSc.
Předpoklady
I005 FJA I
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • Deterministické bezkontextové jazyky (detCFL).
  • Metody syntaktické analýzy detCFL.
  • SLL(k) a LL(k) gramatiky a jazyky, jejich vlastnosti a analyzátory.
  • LR(k), SLR(k) a LALR(k) gramatiky a jazyky, jejich vlastnosti a analyzátory.
  • Vztahy mezi LL, LR a detCFL.
  • (Ne)rozhodnutelné problémy z oblasti detCFL.
  • Vybrané aplikace (překladače, souběžné procesy -- bisimulace).
  • (Ne)rozhodnutelné problémy z oblasti automatů a gramatik vzhledem k bisimulaci.
Literatura
  • AHO, Alfred V., Ravi SETHI a 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. a 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 a Eljas SOISALON-SOININEN. Parsing theory : volume 1 : languages and parsing. Berlin: Springer-Verlag, 1988, 228 s. ISBN 0-387-13720-3. info
  • SIPPU, Seppo a 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
Metody hodnocení
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ů.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/kretinsky/fja2.html
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích zima 1995, zima 1996, zima 1997, podzim 1998, podzim 2000, podzim 2001.