Předmět Formální jazyky a automaty (IB005)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IB005 - Formální jazyky a automaty, Fakulta informatiky, Masarykova univerzita (MU).

Materiál	Typ	Datum	Počet stažení

Cíl

Kurs by měl u studenta rozvinout schopnost abstrakce, seznámit ho s možnostmikonečné specifikace nekonečných objektů, zde konkrétně jazyků, anaučit se aktivně pracovat se základními výpočetními modely a 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 agramatiky. Chomského hierarchie.Konečné automaty a regulární gramatiky; Pumping lemma,Myhillova--Nerodovavěta, minimalizace. Nedeterministickékonečné automaty, vztah k regulárním gramatikám.Vlastnosti regulárníchjazyků; uzávěrové vlastnosti, regulární výrazy, Kleeneho věta,konečnost. Nástin aplikací (grep, ..., lex).Bezkontextové gramatiky a jazyky; transformace bezkontextovýchgramatik, 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 zdolanahoru.Turingovy stroje (TS). Rekursivní a rekursivně vyčíslitelné jazyky afunkce, uzávěrové vlastnosti. Lineárně ohraničené automaty.Nerozhodnutelnost, problém zastavení TS, princip redukce, Postův korespondenční problém, nerozhodnutelné problémy z teorie jazyků.

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 infoGRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997. xv, 716 s. ISBN 1-85032-243-0. infoHOPCROFT, 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. infoCHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984. 331 s. infoKOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0-387-94907-0. infoSIPSER, Michael. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006. xix, 431 p. ISBN 0-534-95097-3. info

Požadavky

IB000 Mat. základy informatiky && ! IB102 Automaty, gramatiky, složitost Znalost problematiky v rozsahu předmětuIB000 Matematické základy informatiky

Garant

prof. RNDr. Mojmír Křetínský, CSc.

Vyučující

prof. RNDr. Mojmír Křetínský, CSc.doc. RNDr. Jiří Barnat, Ph.D.Mgr. Karolína MaláMgr. Lukáš Másilkodoc. RNDr. Jan Strejček, Ph.D.