INFORMACE O KURSU IA006

AUTOMATY

Katedra teorie programování
Fakulta informatiky MU
Podzimní semestr 2021

Počet kreditu: 3 + f-ce ukončeni.

Doporučením pro zápis kursu IA006 je znalost problematiky odpovídající předmětům:

• IB005 (Formální jazyky a automaty) nebo
• IB102 (Automaty, gramatiky [, složitost]).

Syllabus přednášky

Metody syntakticke analyzy detCFL.

LL(k) gramatiky a jazyky, vlastnosti a analyzatory (definice LL(k) gramatiky, vlastnosti LL(1) a SLL(k) gramatik a jejich analyza, LL(k) analyza).

LR(k) gramatiky a jazyky, vlastnosti a analyzatory (definice LR(k) gramatiky, vlastnosti LR(0) a SLR(k) gramatik a jejich analyza, LR(k) analyza a analyza LALR(1) ).

Automaty a gramatiky jako nastroj pro konecnou reprezentaci (nekonecne stavovych) prechodovych systemu; specifikace paralelnich a/nebo sekvencnich procesu, relace bisimulace, tridy procesu a jejich hierarchie.

Konecne automaty a MSO logika (Monadic Second Order Logic)

Konecne automaty nad nekonecnymi slovy. Typy akceptacnich podminek a jejich vzajemne vztahy, $\omega$-regularni jazyky a jejich vlastnosti.

Cas a misto konani

• prednaska: St 10:00-11:50 D1
• cviceni jeden krat za 14 dni 2 hodiny, dle rozvrhu, ktery muzete nalezt i zde (via IS)

Vyucujuci

Prednasky

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

Katedra teorie programovani FI MU
mojmir@fi.muni.cz
mistnost C 419, 4. podlazi, budova C, Botanicka 68a

Cviceni

doc. RNDr. Jan Strejček, PhD.

Katedra teorie programovani FI MU
xstrejc@fi.muni.cz
mistnost C 414, 4. podlazi, budova C, Botanicka 68a

Konzultacni hodiny

• Mojmír Křetínský: streda, 13:45 - 15:15, resp. po domluve
  
• vedouci cviceni: bude oznameno na cvicenich
  

Studijni materialy

• A.V.Aho, M.S.Lam, R.Sethi, J.D.Ullman: Compilers - Principles, Techniques and Tools,
  Addison-Wesley Publ.Comp., 1986; 2nd edition 2007.
• J.E.Hopccroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation
  Addison-Wesley Publ.Comp.,1979.
• J.E.Hopccroft, R.Motwani, J.D.Ullman: Introduction to Automata Theory, Languages and Computation
  Addison-Wesley Publ.Comp., 2nd edition 2001.; 3rd edition 2014
• M.Chytil; Automaty a gramatiky
  SNTL Praha, 1984.
• L.Molnar, M.Ceska, B.Melichar: Gramatiky a jazyky
  ALFA Bratislava / SNTL Praha, 1987.
• Dick Grune a Ceriel J.H. Jacobs: Parsing Techniques - A Practical Guide (LL v kap.8.2, LR v 9.4-9.6)
  kniha dostupna v PDF z adresy freecomputerbooks.com/Parsing-Techniques-A-Practical-Guide.html#downloadLinks
  nebo primo zde
• S.Sippu, E.Soisalon-Soinien: Parsing Theory, Vol.I,II
  Springer-Verlag, 1988 (Vol.I), 1990 (Vol.II).
• W.Thomas: Automata on Infinite Objects, Handbook of Theoret.Computer Science, Vol.B, Chapter 4 (Sections 1,2),
  Elsevier, 1990.
• J.Esparza: Automata Theory: An Algorithmic Approach Lecture notes for a course on finite and omega-automata.
  (dosud nepublikovana kniha, verejne dostupna na strankach autora).
• I.Černá, M.Křetínský a A.Kučera: Automaty a formální jazyky I (materiál ke kursu IB005, FI MU, 2002), el. verze je zde jako ps nebo jako pdf,
  ke zkousce podkapitola 3.4 "Deterministicke zasobnikove automaty".

Studijni materialy podle jednotlivych temat

Syntakticka analyza:
• pom.studij.material ad "LL(1) a SLL(k) gramatiky a jejich analyza" ( ps nebo pdf ).
• pom.studij.material ad "LL(k) gramatiky" - kopie casti podkapitoly z knihy M.Chytil (viz vyse), s.252-259 autorizovany pristup z ISu zde .
• pom.studij.material ad "LR(0) gramatiky" - kopie casti podkapitoly z knihy M.Chytil (viz vyse) , s.220-233 autorizovany pristup z ISu zde a
• pom.studij.material ad "LR(k) gramatiky" - kopie casti podkapitoly z knihy M.Chytil (viz vyse) , s.242-249 autorizovany pristup z ISu zde
• z vyse uvedene knihy Dick Grune a Ceriel J.H. Jacobs: Parsing Techniques - A Practical Guide: LL gramatiky v kap.8.2, LR gramatiky v 9.4-9.6

studijni materialy ke specifikaci procesu a bisimulaci:
• ad specifikace: Grammars as Processes ( ps.gz nebo pdf) - pom.studij.material (casti 1 az 4) - in English.
  
• ad bisimulace: bisimulation (jen velmi stručné 'slides') a detailnější včetně BPA, BPP ( pdf) - pom.studij.material (jen prvních 15 stran; tj. s.102-116) - in English.

studijni materialy k tematu Automaty a logika:
• J.Esparza: z výše uvedené knihy, Part I, Chapter 9 Automata and Logic o logice 1.radu (FO) a monadicke logice 2.radu (MSO) na konečných slovech,
• J.Esparza: z výše uvedené knihy, Part II, Chapter 15, Sec. 15.1 o monadicke logice 2.radu (MSO) na nekonečných slovech, (NEPOVINNE, jen pro zajemce)
  
• ad informandum: slidy z prednasky Vašek Brožek (2010): "Automaty a MSO" ( pdf ) - ponekud jiny zpusob vykladu s vyuzitim tzv. ciste MSO.

studijni studijni materialy k tematu Automaty nad nekonecnymi slovy:

• pom.studij.material "Automaty nad nekonecnymi slovy" ( ps nebo pdf ), nebo
  
• J.Esparza: z výše uvedené knihy, Part II, Chapter 11 a 12 o automatech nad nekonečnými slovy,
  
• W.Thomas: Automata on Infinite Objects, Handbook of Theoret.Computer Science, Vol.B, Chapter 4 (Sections 1,2), Elsevier 1990.

Další pomůcky ke studiu
• PŘÍKLADY k procvičení - pom.studij.material (odkaz do IS)
• Výpočet funkce First a Follow, a LR analýza pomocí nástroje JGAF - SW studijní pomůcka
.

Pozadavky na absolvovani predmetu

V prubehu semestru se kona 1 pisemna prace (dale ref.jako "vnitrosemetralni pisemka"). Dalsi pisemna prace ("zaverecna pisemna zkouska") se kona ve zkouskovem obdobi (předtermín po domluvě a dle kapacitních možností na FI). Maximalni mozny zapocitavany zisk z obou pisemnych praci je 100 bodu.

Za vnitrosemetralni pisemku lze ziskat 20 bodu. Body ziskane z teto prace se zapocitavaji do celkoveho hodnoceni predmetu (viz nize). Za zaverecnou pisemnou zkousku lze ziskat maximalne 80 bodu. Pouziti literatury a poznamek neni na pisemkach povoleno.

Hodnoceni:
Zkouška: A: alespon 87 b., B: alespon 79 b., C: alespon 71 b., D: alespon 63, E: alespon 55 b.
Zapocet: alespon 50 b.

Terminy pisemek

1.písemka (vnitrosemestrální): datum konani bude oznameno pozdeji, alespon tyden predem, odhad: 1.-3. tyden listopadu. Délka trvání - prozatímní odhad 90 minut; bude nutné se přihlásit přes IS.

Téma:
(A) vše o LL(1), SLL(k), LL(k) - nejen konstrukce analyzátorů, ale i definice a vlastnosti (včetně důkazů). LR(0) a SLR(k) - totéž, co ad LL(k);
(B) deterministické zásobníkové automaty a deterministické bezkontextové jazyky, vizte výše "Studijní materiály", skripta Automaty a formální jazyky I (skripta pro IB005 resp. IB102), podkapitola 3.4.

Závěrečné písemné zkoušky (únor) budou oznameny pozdeji.

DETAILY a PŘIHLÁŠKY budou zveřejněny v ISu nejpozději 2 týdny před začátkem zkouškového období.