Formálne jazyky a automaty

Čo sa na tomto predmete
naučíš?

zimný
2. ročník
6 kreditov
Algoritmizácia

V tomto kurze sa ponoríš do teórie formálnych jazykov a automatov. Začneš tým, čo je jazyk ako množina slov, naučíš sa operácie nad jazykmi a ako ich formalizovať. Potom sa oboznámiš s gramatikami a ich typmi v rámci Chomského hierarchie.

Ďalej sa budeš venovať regulárnym gramatikám, konečným automatov – deterministickým aj nedeterministickým – a naučíš sa ich minimalizovať. Spolu s tým pochopíš princípy Moorovho a Mealyho stroja.

Získané poznatky prehĺbiš pri štúdiu regulárnych výrazov, a naučíš sa, čo znamená nutná a postačujúca podmienka regulárnosti. Pokročíš k bezkontextovým jazykom a ich gramatikám, ako aj k zásobníkovým automatom.

Prejdeš si metódy syntaktickej analýzy (zhora nadol a zdola nahor) a pozrieš sa na doménovo-špecifické jazyky v regulárnej a bezkontextovej oblasti. Následne sa dotkneš kontextových jazykov, Turingovho stroja, lineárne ohraničeného automatu a nakoniec rekurzivity a Turingovej tézy.

Domáca príprava pozostáva z pravidelného štúdia materiálov, riešenia úloh v e-learningovom kurze a príprav na priebežné testy a záverečnú skúšku.

PROJEKTY, KTORÉ VYTVORILI
ŠTUDENTI