INFORMACE O KURSU IA006

AUTOMATY

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

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 nad nekonecnymi slovy. Typy akceptacnich podminek a jejich vzaemne vztahy, $\omega$-regularni jazyky a jejich vlastnosti.

Konecne automaty a MSO logika (Monadic Second Order Logic)

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 421, 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 421, 4. podlazi, budova B, Botanicka 68a

RNDr. Nikola Beneš

Laboratoř Paradise FI MU
xbenes3@fi.muni.cz
mistnost C 408, 4. podlazi, budova C, Botanicka 68a

RNDr. Milan Češka

Laboratoř Paradise FI MU
xceska@fi.muni.cz
mistnost C 408, 4. podlazi, budova C, Botanicka 68a

Bc. Filip Štefaňák

FI MU
xstefan5@fi.muni.cz

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
• J.E.Hopccroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation
  Addison-Wesley Publ.Comp.,1979, 2.(modif.)vydani 2000
• J.E.Hopccroft, R.Motwani, J.D.Ullman: Introduction to Automata Theory, Languages and Computation
  Addison-Wesley Publ.Comp., 2.vydani 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. 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): ctvrtek 3.11.2011 od 18:00 resp. 18:55; (delka trvani - prozatimni odhad 90 minut); bude nutne se prihlasit pres IS.
Poslucharny se zacatkem 18:00 prednostne pro ty, kteri denne do Brna dojizdi. Z techto poslucharen nebude povoleno se vzdalit pred 19:05.
Tema: vse o 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:

predtermin: v patek 16. 12. 2011, 17:00-19:30 D1, (v pripade vetsiho zajmu i v D3)

radne a opravne terminy:

• 18.1.,   10:00-12:30; D1, (D2, D3)
• 31.1.,   10:00-12:30; D1, (D2, D3)
•   9.2.,   10:00-12:30; D1, (D2, D3)

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