INFORMACE O KURSU IB005

FORMÁLNÍ  JAZYKY  A  AUTOMATY 

Katedra teorie programování
Fakulta informatiky MU
semestr: jaro 2013

Syllabus prednasky

Predpokladem pro zapis prednasky IB005 je znalost pojmu v rozsahu prednasky IB000 Matematické základy informatiky

Pojem jazyka a problem jeho konecne specifikace.
Prepisovaci systemy, gramatiky. Chomskeho hierarchie.
Konecne automaty (deterministicke a nedeterministicke) a regularni jazyky. Vzajemne vztahy konecnych automatu a regularnich gramatik.
Vlastnosti regularnich jazyku.
Bezkontextove gramatiky a zasobnikove automaty a jejich vzajemne vztahy.
Vlastnosti bezkontextovych jazyku.
Deterministicke zasobnikove automaty a bezkontextove jazyky (detCFL) a jejich zakladni vlastnosti.
Turingovy stroje a jazyky typu 0 a jejich vzajemne vztahy. Vycislitelne jazyky a funkce.

Cas a misto konani

Vyučující

Přednášky

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

Katedra teorie programování FI MU
mojmir@fi.muni.cz
místnost B408, Botanická 68a

Cvičení

doc. RNDr. Jiří Barnat, PhD

Katedra teorie programovani FI MU
xbarnat@fi.muni.cz
místnost B421, Botanická 68a

RNDr. Milan Češka, Ph.D.

Katedra teorie programovani FI MU
xceska@fi.muni.cz
místnost C516, Botanická 68a

Mgr. František Blahoudek

FI MU
fandik@mail.muni.cz
místnost G219, Gotex, Šumavská 15

Konzultacni hodiny

• prof. RNDr. Mojmír Křetínský, CSc.: pátek, 12:30 - 14:30
  
• doc. RNDr. Jiří Barnat, Ph.D. : bude oznámeno na cvičeních
  
• RNDr. Milan Češka, Ph.D. : bude oznámeno na cvičeních
  
• Mgr. František Blahoudek : bude oznámeno na cvičeních
  

Studijni materialy

• I.Černá, M.Křetínský a A.Kučera: Automaty a formální jazyky I
  materiál ke kursu IB005, FI MU, 2002.
  Elektronicka verze je zde jako ps nebo jako pdf ,
  hard copy v knihkupectví "U Marečka".
• stručný dodatek o LL(1) gramatikách je zde (ps) ; kopie též v knihkupectví "U Marečka"
• P. Jančar: Teoretická informatika, VŠB-TU Ostrava 2007
  materiál určený pro samostudium, ke stažení zde
• J.Gruska: Foundations of Computing. Thomson International Computer Press, 1997
• M.A.Harrison: Introduction to Formal Language Theory
  Addison-Wesley Publ.Comp., 1978
• 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, 2nd ed.
  Addison-Wesley Publ.Comp.,2001
• M.Chytil; Automaty a gramatiky
  SNTL Praha, 1984
• D.Kozen: Automata and computability
  Springer, 1997
• A.P.Parkes: A concise introduction to languages and machines (Undergraduate topics in computer science), Springer, 2008
• ZKUSTO
• Kurs na VSB v Ostravě
• Kurs na MFF v Praze
• K dispozici jsou též příklady k procvičení:
  sbírka "Příklady k cvičením" a
  další (níže uvedené) ukoly k procviceni, vcetne jejich vzorovych reseni. Dobrá rada: úkoly zkoušejte řešit samostatně a až následně konzultujte Vaše řešení s řešením vzorovým!

Pozadavky na absolvovani predmetu

Za vnitrosemestralni pisemku lze ziskat 20 bodu.
Nove: vnitrosemestralni pisemka se kona 4.4., 14:00, D3.
Na tuto pisemku bude nutno se prihlasit via IS.
Body ziskane z teto prace se zapocitavaji do celkoveho hodnoceni predmetu (viz nize). Pouziti literatury a poznamek neni povoleno.

Zkouska: Závěrečná zkouska je pisemna a lze za ni ziskat maximalne 80 bodu. Pouziti literatury a poznamek neni povoleno.

Terminy zaverecne zkousky: 28.5., radne i opravne: 10.6., 18.6. a 26.6.; prihlaseni via IS.

Hodnoceni: maximalni mozny zapocitavany zisk z obou pisemnych praci je 100 b.
A(vyborne): alespon 87 b., B: alespon 79 b., C: alespon 71 b., D: alespon 63, E: alespon 55 b.

Domaci ukoly k procviceni

• Cviceni 1 a Reseni 1
• Cviceni 2 a Reseni 2
• Cviceni 3 a Reseni 3
• Cviceni 4 a Reseni 4
• Cviceni 5 a Reseni 5
• Cviceni 6 a Reseni 6
• Cviceni 7 a Reseni 7
• Cviceni 8 a Reseni 8
• Cviceni 9 a Reseni 9
• Cviceni 10 a Reseni 10
• DALSI PRIKLADY
• sbírka "Příklady k cvičením" (referencovaná již výše v seznamu studijních materiálů)

Aktuality

Pro Vasi info: minule pisemky z IB005

• 1.pisemka v LS'98
• 2.pisemka v LS'98
• 2.pisemka v LS'97
• nahradni 2.pisemka v LS'97 (pro nemocne v radnem terminu)
• 1.vnitrosemestralni pisemka v LS'99
• 1.vnitrosemestralni pisemka v LS'99
• 2.vnitrosemestralni pisemka v LS'99
• 2.vnitrosemestralni pisemka v LS'99
• Durazne upozornuji, ze typy prikladu mohou byt jine nez ty, ktere byly v minulých letech.