• slidy_4p.pdf

• Cviceni 0 (v tydnu od 27.9.2004): zde neni priprava, budou zopakovany potrebne algebraicke pojmy a dukazy matem. indukci cvic_00.ps , cvic_00.pdf
• Cviceni 1 (v tydnu od 4.10.2004): cvic_01_2p.ps , cvic_01_2p.pdf
• Cviceni 2 (v tydnu od 11.10.2004): cvic_02_2p.ps , cvic_02_2p.pdf
• Cviceni 3 (v tydnu od 18.10.2004): cvic_03.ps , cvic_03.pdf
• Cviceni 4 (v tydnu od 25.10.2004): cvic_04_2p.ps , cvic_04_2p.pdf
• Cviceni 5 (v tydnu od 1.11.2004): cvic_05_2p.ps , cvic_05_2p.pdf
• Cviceni 6 (v tydnu od 8.11.2004): cvic_06_2p.ps , cvic_06_2p.pdf
• Cviceni 7 (v tydnu od 22.11.2004): cvic_07_2p.ps , cvic_07_2p.pdf
• Cviceni 8 (v tydnu od 29.11.2004): cvic_08.ps , cvic_08.pdf
• Cviceni 9 (v tydnu od 6.12.2004): cvic_09.ps , cvic_09.pdf
• Cviceni 10 (v tydnu od 13.12.2004): cvic_10.ps , cvic_10.pdf
• Cviceni 11 (v tydnu od 3.1.2005): cvic_11.ps , cvic_11.pdf
• Cviceni 12 (v tydnu od 10.1.2005): cvic_12_2p.ps , cvic_12_2p.pdf pripadne dokonceni drivejsich prikladu, diskuse ilustracniho testu, odevzdani pisemnych reseni cviceni.

Pozadavky k ziskani kreditu, hodnoceni:

• ZAPOCET
  • Za kazde cviceni, na ktere si posluchac donese (dostatecnou) pisemnou pripravu a bude na nem pripraven reseni a problemy aktivne diskutovat, ziska 1 bod - maximalne vsak 10 bodu za semestr.
  • Podminkou zapoctu je odevzdani prehledne zpracovaneho pisemneho reseni vsech prikladu zadanych pro vsechna cviceni v semestru. Reseni musi byt psano vlastni rukou resitele (nikoli vystup z elektronicke podoby ci podobne) a musi byt odevzdano nejpozdeji na poslednim cviceni v semestru !
  • Poznamka. I ten, kdo se nekterych cviceni nezucastni, ci kdo na ne nebude dostatecne pripraven, musi tedy pro ziskani zapoctu odevzdat i reseni uloh prislusnych k temto cvicenim. Body za takova cviceni ovsem nedostane. Muze se tedy i stat, ze nekdo splni podminky zapoctu, ale neziska zadny bod.
• ZKOUSKA
  • Jen posluchaci, kteri splni podminky zapoctu, se mohou dostavit k napsani zkusebniho testu ve zkouskovem obdobi.
  • Ve zkusebnim testu bude mozne ziskat max. 90 bodu.
  • K vysledku zkousky se prictou body za zapocet (0-10) a celkove hodnoceni je urceno standardne: 86-100 vyborne, 66-85 velmi dobre, 51-65 dobre, 0-50 nevyhovel.
  • O obsahu zaverecneho testu si lze udelat pribliznou predstavu z materialu, ktery si zde muzete stahnout jako ps-soubor ci pdf-soubor (5 stran): iltest_01_2p.ps , iltest_01_2p.pdf .
  • Poznamka pro posluchace v bakalarskem studiu: za spravne vyreseny priklad bude prislusne bodove hodnoceni zvyseno az dvojnasobne; tim je reflektovana mensi narocnost zkousky v tomto studiu.

Strucny obsah kursu:

1. Uvod ke kursu. Konecny automat.
2. Navrh konecnych automatu. Regularni operace. Nedeterminismus.
3. Vztah deterministickych a nedeterministickych konecnych automatu. Uzaverove tridy regularnich jazyku.
4. Regularni vyrazy a jejich ekvivalence s konecnymi automaty.
5. Minimalni konecne automaty a algoritmus minimalizace.
6. Neregularni jazyky. Pumping lemma pro regularni jazyky.
7. Bezkontextove gramatiky a jazyky, derivacni stromy, jednoznacnost, uloha syntakticke analyzy. Redukovane gramatiky.
8. Nevypoustejici gramatiky. Chomskeho normalni forma. Odstraneni leve rekurze. Greibachove normalni forma
9. Zasobnikove automaty a jejich ekvivalence s bezkontextovymi gramatikami.
10. Nebezkontextove jazyky. Pumping lemma pro bezkontextove jazyky.
11. Uzaverove vlastnosti tridy bezkontextovych jazyku. Deterministicke zasobnikove automaty.
12. Obecne gramatiky, Chomskeho hiearchie. Konecne automaty a regularni gramatiky. Turingovy stroje.
13. Nedeterministicke Turingovy stroje. Turingovy stroje a obecne gramatiky. Linearne omezene automaty a kontextove jazyky.
14. Shrnuti s pripadnym naznacenim dalsich smeru teorie.

Doporucena literatura:

• M. Chytil: Automaty a gramatiky, SNTL, Praha 1984
• J. Hopcroft, J. Ullman: Formal languages and their relation to automata - slov. preklad Formalne jazyky a automaty, Alfa, Bratislava 1978
• Molnar, Ceska, Melichar: Gramatiky a jazyky, Alfa-SNTL 1987
• Krome vyse uvedenych existuji i dalsi moznosti studia uvedene problematiky v cestine ci slovenstine. Neuvadime cizojazycnou literaturu kvuli jeji tezke dostupnosti -- na druhe strane ``surfovanim'' na Webu je samozrejme mozne ziskat mnohe uzitecne texty v anglictine.
• ONLINE: Černá, Křetínský, Kučera: Automaty a formální jazyky I, FIMU Brno (odkaz zde přidán se souhlasem M. Křetínského).