INFORMACE O KURSU IA006

AUTOMATY

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

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

Doporučením pro zápis kursu IA006 je znalost problematiky odpovídající predmetum:

• IB005 (Formalni jazyky a automaty) a
• IB107 (Vycislitelnost a slozitost).

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 vzaemne vztahy, $\omega$-regularni jazyky a jejich vlastnosti.

Cas a misto konani

• prednaska: St 14:00-15: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 B 408, 4. podlazi, budova B (vlevo), Botanicka 68a

Cviceni

doc. RNDr. Jiří Barnat, PhD.

Katedra teorie programovani FI MU
xbarnat@fi.muni.cz
mistnost B 415, 4. podlazi, budova B, Botanicka 68a

RNDr. Vojěch Řehák, PhD.

Institut teoretické informatiky (ITI) FI MU
xrehak@fi.muni.cz
mistnost G 208 (vstup pres G 217), 1. patro, budova D, Sumavska 15

RNDr. Jan Strejček, PhD.

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

RNDr. Tomáš Brázdil, PhD.

Institut teoretické informatiky (ITI) FI MU
xbrazdil@fi.muni.cz
mistnost G 208 (vstup pres G 217), 1. patro, budova D, Sumavska 15

Mgr. Jan Obdržálek, PhD.

Institut teoretické informatiky (ITI) FI MU
xobdrzal@fi.muni.cz
mistnost G 208 (vstup pres G 217), 1. patro, budova D, Sumavska 15

Konzultacni hodiny

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

Studijni materialy

• A.V.Aho, R.Sethi,J.D.Ullman:Compilers - Principles, Techniques and Tools, Addison-Wesley Publ.Comp. 1986; 2nd edition. 2006
• 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
• 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
  kniha dostupna v PDF i PostScript (LL v kap.8.2, LR v 9.4-9.6)
• 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
• PŘÍKLADY k procvičení - pom.studij.material
• pom.studij.material ad "LL(1) a SLL(k) gramatiky a jejich analyza" ( ps nebo pdf ) -- oprava 2 preklepu 22.9. 09:45
• 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
• ke specifikaci procesu a bisimulaci doporucuji:
  ad specifikace: Grammars as Processes ( ps.gz nebo pdf) - pom.studij.material (casti 1 az 4) - in English
  ad bisimulace: bisimulation and normed BPA ( ps nebo pdf) - pom.studij.material (jen do str.18) - in English
• studij.material k tematu Automaty a logika
  text J.Esparza: Automata and Logic o logice 1.radu (FO) a monadicke logice 2.radu (MSO) na slovech, in English)
  ad informandum: slidy z prednasky Vašek Brožek (2010): "Automaty a MSO" ( pdf ) - ponekud jiny zpusob vykladu s vyuzitim tzv. ciste MSO.
• pom.studij.material "Automaty nad nekonecnymi slovy" ( ps nebo pdf )
• ZKUSTO : jen synt.analyzy typu LL a LR (obsahuje chyby; k nalezeni v odd."II.rocnik", pod nazvem Automaty a formalni jazyky II.)

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.pisemka (vnitrosemestralni): patek 2.11.2012 od 17:00 Delka trvani - prozatimni odhad 100 minut; bude nutne se prihlasit pres IS.
Tema: vse o LL(1), SLL(k), LL(k) - nejen kontrukce analyzatoru, ale i definice a vlastnosti (vc.dukazu). LR(0) a SLR(k) - totez, co ad LL(k).

Zaverecne pisemne zkousky:

BUD (v pripade zajmu a moznosti nalezeni volnych poslucharen) predtermin pred vanocemi a dalsi tri radne a opravne terminy 17.1., 28.1. a 7.2 (vizte nize),

ANEBO ctyri radne a opravne terminy:

•   4.1.,   10:00-12:30; D1, (D2, D3)
• 17.1.,   10:00-12:30; D1, (D2, D3)
• 28.1.,   10:00-12:30; D1, (D2, D3)
•   7.2.,   11:00-13:30; D1, (D2, D3)

DETAILY a PRIHLASKY budou zverejneny v ISu nejpozdeji 2 tydny pred zacatkem zkouskoveho obdobi