I006 Formální jazyky a automaty II

Fakulta informatiky
podzim 2001
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í)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící), prof. RNDr. Ivana Černá, CSc. (zástupce)
RNDr. Jaroslav Ráček, Ph.D. (cvičící), prof. RNDr. Ivana Černá, CSc. (zástupce)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící), prof. RNDr. Ivana Černá, CSc. (zástupce)
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.
Rozvrh
St 15:00–17:50 D1
  • Rozvrh seminárních/paralelních skupin:
I006/02: každý sudý čtvrtek 9:00–10:50 B007, J. Barnat
I006/06: každý sudý čtvrtek 9:00–10:50 B003, V. Řehák
I006/01: každý lichý čtvrtek 9:00–10:50 B007, J. Barnat
I006/05: každý lichý čtvrtek 9:00–10:50 B003, V. Řehák
I006/04: každý sudý čtvrtek 15:00–16:50 B007, J. Barnat
I006/08: každý sudý čtvrtek 15:00–16:50 B011, V. Řehák
I006/03: každý lichý čtvrtek 15:00–16:50 B007, J. Barnat
I006/07: každý lichý čtvrtek 15:00–16:50 B011, V. Řehák
Předpoklady
I005 FJA I || I505 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
Anotace
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,...)
Klíčová témata
  • Deterministické bezkontextové jazyky (DCFL) 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 DCFL.
  • (Ne)rozhodnutelné problémy z oblasti DCFL.
  • Specifikace přechodových systémů; bisimulace; vybrané (ne)rozhodnutelné problémy se vztahem k verifikaci procesů.
  • Další typy automatů (s výstupem, nad nekonecnymi slovy, stromové) a jejich aplikace.
Studijní zdroje a 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
  • 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 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
Způsob ověření výstupů z učení a požadavky na ukončení
Během semestru jedna pisemná zkouška. Závěrečná zkouška je rovněž písemná; obě bez použití materiálů.
Navazující předměty
Odkaz a informace vyučujících
http://www.fi.muni.cz/usr/kretinsky/fja2.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích zima 1995, zima 1996, zima 1997, podzim 1998, podzim 1999, podzim 2000.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/podzim2001/I006