FI:IA006 Automaty - Informace o předmětu

IA006 Vybrané kapitoly z teorie automatů

Rozsah

2/1/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučováno kontaktně

Vyučující

prof. RNDr. Mojmír Křetínský, CSc. (přednášející)
Mgr. Juraj Major (cvičící)
RNDr. David Klaška (pomocník)

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

St 25. 9. až St 18. 12. St 10:00–11:50 A218

• Rozvrh seminárních/paralelních skupin:

IA006/01: Čt 26. 9. až Čt 5. 12. každý lichý čtvrtek 14:00–15:50 A318; a Čt 12. 12. 14:00–15:50 A318, J. Major

Předpoklady

Znalost problematiky v rozsahu předmětu IB005 - Formální jazyky a automaty a IB107 - Vyčíslitelnost a složitost

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 256 stud.
Momentální stav registrace a zápisu: zapsáno: 10/256, pouze zareg.: 0/256, pouze zareg. s předností (mateřské obory): 0/256

Mateřské obory/plány

předmět má 29 mateřských oborů, zobrazit

Cíle předmětu

Cílem je seznámit studenty s pokročilejšími partiemi teorie automatů, a to jak aplikacemi klasické teorie automatů a gramatik (metody syntaktické analýzy deterministických bezkontextových jazyků), problematikou použití automatů pro specifikaci procesů (bisimulační ekvivalence, vztah automatů a MSO logiky), tak i s automaty nad nekonečnými slovy a jejich použitím. Na konci tohoto kurzu bude student schopen předkládat odůvodněná rozhodnutí o modelech relevatních pro danou oblast a porozumět metodám a technikám jejich použití.

Výstupy z učení

Na konci tohoto kurzu bude student schopen demostrovat plné porozumění vybraných pokročilých partií z teorie automatů a předkládat odůvodněná rozhodnutí o modelech relevatních pro danou oblast a porozumět metodám a technikám jejich použití.

Osnova

• Deterministické bezkontextové jazyky (DCFL) a jejich syntaktická analýza.
• LL(k) gramatiky a jazyky; vlastnosti a analyzátory.
• LR(k) gramatiky a jazyky; vlastnosti a analyzátory.
• Vztahy mezi LL, LR a DCFL. (Ne)rozhodnutelné problémy z oblasti DCFL.
• Nekonečně stavové přechodové systémy a nedeterminismus - modelováníé procesů, bisimulace, vybrané rozhodnutelné problémy se vztahem k verifikaci procesů.
• Konečné automaty a MSO logika (monadická logika 2. řádu)
• Automaty nad nekonečnými slovy: nekonečná slova, regulární (racionální) množiny nekonečných slov.
• Automaty: deterministické a nedeterministické Büchiho automaty, Mullerovy Rabinovy a Streetovy automaty. McNaughtonova věta. Vzájemné vztahy.

Literatura

• 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
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. 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
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Výukové metody

přednášky, cvičení, samostudium. Volitelné domácí úlohy.

Metody hodnocení

Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou 25%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.

Navazující předměty

• IA040 Modální a temporální logiky procesů
• IA041 Teorie a specifikace procesů
• PA008 Překladače

Informace učitele

http://www.fi.muni.cz/usr/kretinsky/fja2.html

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2024/IA006