IB005 Formální jazyky a automaty I
Fakulta informatikyjaro 2011
- Rozsah
- 4/2. 6 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
- Vyučující
- prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
prof. RNDr. Jiří Barnat, Ph.D. (cvičící)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
RNDr. Nikola Beneš, Ph.D. (cvičící)
RNDr. Jana Tůmová, Ph.D. (pomocník)
Mgr. Bc. Tomáš Janík (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
- St 10:00–11:50 D2, Čt 14:00–15:50 D1
- Rozvrh seminárních/paralelních skupin:
IB005/01: Po 12:00–13:50 C511, J. Barnat
IB005/02: Čt 12:00–13:50 C511, J. Barnat
IB005/03: St 16:00–17:50 B204, J. Strejček - Předpoklady
- MB005 Základy matematiky && ! IB102 Automaty a gramatiky
Znalost problematiky v rozsahu předmětu IB005 Úvod do informatiky MB005 Základy matematiky - 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
- předmět má 22 mateřských oborů, zobrazit
- Cíle předmětu
- Kurs by měl u studenta ozvinout schopnost abstrakce, seznámit ho s možnostmi konečné specifikace nekonečných objektů, zde konkrétně jazyků, a naučit se aktivně pracovat se základními výpočetními modelyů vytvořit předpoklady pro schopnosti vlastní formulace abstrakcí a jejich porozumění.
- Osnova
- Pojem jazyka a problém specifikace (nekonečných) jazyků; základní operace nad jazyky. Přepisovací systémy a gramatiky. Chomského hierarchie.
- Konečné automaty a regulární gramatiky; Pumping lemma, Myhillova--Nerodova věta, minimalizace. Nedeterministické konečné automaty, vztah k regulárním gramatikám.
- Vlastnosti regulárních jazyků; uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost. Nástin aplikací (grep, ..., lex).
- Bezkontextové gramatiky a jazyky; transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti; konečnost a regularita.
- Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám; nedeterministická syntaktická analýza shora dolů a zdola nahoru.
- Turingovy stroje. Rekursivní a rekursivně vyčíslitelné jazyky a funkce, uzávěrové vlastnosti. Lineárně ohraničené automaty.
- Deterministické zásobníkové automaty a deterministické bezkontextové jazyky; vlastnosti. Nástin aplikací (deterministické analýza shora -- princip; zdola -- nástroj yacc/bison).
- Literatura
- ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Elportál. Brno: Masarykova univerzita, 2006. ISSN 1802-128X. URL info
- 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
- SIPSER, Michael. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006, xix, 431. ISBN 0534950973. info
- Výukové metody
- přednášky, cvičení, samostudium. Volitelné domácí úlohy.
- Metody hodnocení
- 2 písemné zkoušky během semestru a závěrečná písemná zkouška. Výsledky vnitrosemestrálních písemek se započítávají do výsledného hodnocení s vahou 15% za každou písemku. Všechny písemky bez pomocných materiálů.
- Navazující předměty
- Informace učitele
- http://www.fi.muni.cz/usr/kretinsky/fja1.html
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně. - Nachází se v prerekvizitách jiných předmětů
- Statistika zápisu (jaro 2011, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2011/IB005