456-0500/01 – Teorie jazyků a automatů - Bc. (TJAb)
Garantující katedra | Katedra informatiky | Kredity | 8 |
Garant předmětu | prof. RNDr. Petr Jančar, CSc. | Garant verze předmětu | prof. RNDr. Petr Jančar, CSc. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
Ročník | | Semestr | zimní |
| | Jazyk výuky | čeština |
Rok zavedení | 1998/1999 | Rok zrušení | 2003/2004 |
Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je zvládnutí základních pojmů a metod teorie jazyků a automatů, speciálně konečných automatů a bezkontextových jazyků.
Vyučovací metody
Anotace
Kurs je venovan zakladnim partiim (matematicke) teorie automatu a jazyku, se
soustredenim se na konecne automaty a bezkontextove jazyky. Cilem kursu je
jednak objasneni pojmu, vysledku a metod, ktere jsou vyuzivany v ruznych
oblastech aplikovane informatiky (napr. pri vyhledavani vzorku v textu ci pri
navrhu a realizaci prekladacu), a take demonstrovani uzitecnosti
formalizovaneho (abstraktniho) pristupu pri reseni (praktickych) problemu.
Povinná 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.
Doporučená literatura:
Pracovní text ke kursu zpracovaný P. Jančarem
(na http://www.cs.vsb.cz/jancar/TJAA/tjaa.htm
odkazy na soubor clk_tja01_2p.ps a alternativne
na clk_tja01_2p.pdf)
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Uvod ke kursu. Konecny automat.
Navrh konecnych automatu. Regularni operace. Nedeterminismus.
Vztah deterministickych a nedeterministickych konecnych automatu. Uzaverove tridy regularnich jazyku.
Regularni vyrazy a jejich ekvivalence s konecnymi automaty.
Minimalni konecne automaty a algoritmus minimalizace.
Neregularni jazyky. Pumping lemma pro regularni jazyky.
Bezkontextove gramatiky a jazyky, stromy odvozeni, jednoznacnost, uloha syntakticke analyzy.
Redukovane gramatiky, Chomskeho normalni forma.
Zasobnikove automaty a jejich ekvivalence s bezkontextovymi gramatikami.
Uzaverove vlastnosti tridy bezkontextovych jazyku. Deterministicke zasobnikove
automaty.
Nebezkontextove jazyky. Pumping lemma pro bezkontextove jazyky.
Obecne gramatiky, Chomskeho hiearchie. Konecne automaty a regularni gramatiky.
Turingovy stroje.
Rekurzivni a rekurzivne spocetne jazyky. Linearne omezene automaty a kontextove jazyky.
Zaver kursu.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.