I006 Formální jazyky a automaty II
Fakulta informatikypodzim 2000
- 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. - 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
- Informatika (program FI, B-IN)
- Informatika (program FI, M-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
- Výpočetní technika (program FI, B-IN)
- 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.
- Automaty jako speciální instance přechodových systémů; relace bisimulace, souběžné procesy - jejich třídy a vztahy; vybrané rozhodnutelné a nerozhodnutelné problémy se vztahem k verifikaci procesů.
- Další typy automatů a jejich aplikace (automaty s výstupem, automaty pracujici nad nekonecnymi slovy, stromové automaty).
- 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. Závěrečná zkouška je rovněž písemná; obě 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.
- Statistika zápisu (podzim 2000, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2000/I006