I505 Formální jazyky a automaty I

Fakulta informatiky
jaro 2001
Rozsah
3/2. 5 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. Jiří Barnat, Ph.D. (cvičící)
Mgr. Radek Czerný (cvičící)
prof. RNDr. Ivana Černá, CSc. (cvičící)
Mgr. BcA. Robert Král, Ph.D. (cvičící)
Mgr. Pavel Krčál (cvičící)
Mgr. Jaroslav Műller (cvičící)
Mgr. Miloslav Nepil, Ph.D. (cvičící)
doc. Mgr. Jan Obdržálek, PhD. (cvičící)
doc. Mgr. Radek Pelánek, Ph.D. (cvičící)
RNDr. Jaroslav Ráček, Ph.D. (cvičící)
Roman Rožník (cvičící)
doc. RNDr. Vojtěch Řehák, Ph.D. (cvičící)
Mgr. Radek Sedláček, Ph.D. (cvičící)
Mgr. Oldřich Stražovský (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.
Rozvrh
Po 12:00–14:50 D1, St 15:00–17:50 D1
  • Rozvrh seminárních/paralelních skupin:
I505/NEMOC: Rozvrh nebyl do ISu vložen. M. Křetínský
I505/LF2p: Rozvrh nebyl do ISu vložen. M. Křetínský
I505/LF4p: Rozvrh nebyl do ISu vložen. M. Křetínský
I505/S1: Rozvrh nebyl do ISu vložen. V. Řehák
I505/S2: Rozvrh nebyl do ISu vložen. R. Pelánek
I505/S3: Rozvrh nebyl do ISu vložen. J. Műller
I505/S4: Rozvrh nebyl do ISu vložen. V. Řehák
I505/S5: Rozvrh nebyl do ISu vložen. R. Sedláček
I505/S6_A: Rozvrh nebyl do ISu vložen. I. Černá
I505/S7: Rozvrh nebyl do ISu vložen. P. Krčál
I505/S8: Rozvrh nebyl do ISu vložen. R. Rožník
I505/S9: Rozvrh nebyl do ISu vložen. J. Obdržálek
I505/S10: Rozvrh nebyl do ISu vložen. J. Barnat
I505/S11: Rozvrh nebyl do ISu vložen. J. Ráček
I505/S12: Rozvrh nebyl do ISu vložen. J. Barnat
I505/S13: Rozvrh nebyl do ISu vložen. J. Ráček
I505/S14: Rozvrh nebyl do ISu vložen. M. Nepil
I505/S15: Rozvrh nebyl do ISu vložen. R. Král
I505/S16: Rozvrh nebyl do ISu vložen. R. Czerný
I505/S17: Rozvrh nebyl do ISu vložen. O. Stražovský
I505/S18: Rozvrh nebyl do ISu vložen. O. Stražovský
I505/P1_po: Rozvrh nebyl do ISu vložen. M. Křetínský
I505/P2_Str: Rozvrh nebyl do ISu vložen. M. Křetínský
Předpoklady
I000 Úvod do informatiky &&( M005 Základy matematiky || M036 Úvod do diskr. matematiky || PřF:M1500 Algebra I ) && (! 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
  • Pojem jazyka a gramatiky. Chomského hierarchie.
  • Konečné automaty a regulární gramatiky.
  • Vlastnosti regulárních jazyků.
  • Bezkontextové gramatiky a zásobníkové automaty.
  • Vlastnosti bezkontextových jazyků.
  • Deterministické zásobníkové automaty.
  • Turingovy stroje. Vyčíslitelné jazyky a funkce.
  • Nerozhodnutelnost, (parciální) rozhodnutelnost. Problém zastavení TS.
  • Postův korespondenční problém. Algoritmicky nerozhodnutelné problémy z teorie jazyků.
Literatura
  • I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. 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
Metody hodnocení
2 písemné zkoušky během semestru a závěrečná písemná zkouška.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/kretinsky/fja1.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2000, jaro 2002.