Zoznam všetkých cieľov

Cvičenia

1. týždeň: Úvod do formálnych jazykov. Operácie nad jazykmi a ich abecedami. Úvod do regulárnych výrazov.

1. Oboznámiť sa s organizáciou cvičení predmetu Formálne jazyky a podmienkami udelenia zápočtu.
2. Definovať základné pojmy teórie formálnych jazykov.
3. Oboznámiť sa s regulárnymi výrazmi.
4. Prakticky precvičiť zostavenie vybraných regulárnych výrazov.

2. týždeň: Konečnostavové akceptory. DKA

1. Zopakovať si tvorbu regulárnych výrazov na základe slovnej špecifikácie.
2. Definovať deterministický konečnostavovový automat (DKA) ako ekvivalentný spôsob určenia regulárneho jazyka.
3. Konštruovať DKA na základe zadaného regulárneho výrazu.
4. Implementovať DKA pre daný regulárny výraz vo vyššom programovacom jazyku (tvorba primitívneho jazykového procesora).

3. týždeň: Konečnostavové akceptory. NKA, DKA a vzťah medzi nimi.

1. Zopakovať si definíciu DKA a porozumieť jeho minimalizácii.
2. Definovať nedeterministický konečnostavovový automat (NKA) ako rozšírenie DKA. Porovnať tieto dva druhy konečnostavových automatov.
3. NKA ako alternatívny spôsob definície regulárneho jazyka (konštruovať NKA na základe zadaného regulárneho výrazu).
4. Implementovať NKA pre daný regulárny výraz vo vyššom programovacom jazyku.

4. týždeň: Konečnostavové akceptory – determinizácia. Pumpovacia lema.

1. Definovať princíp determinizácie NKA (konštrukcia ekvivalentného DKA na základe zadaného NKA).
2. Definovať pumpovaciu lemu pre regulárne jazyky.
3. Prezentovať postup dôkazu neregularity jazyka na základe pumpovacej lémy.

5. týždeň: Zápočtová písoma A. Úvod do formálnych gramatík.

1. Zápočtová písoma A.
2. Oboznámiť sa s definíciami základných pojmov z oblasti formálnych gramatík.
3. Definovať Backusova-Naurova forma (BNF) a rozšírenú Backusova-Naurova forma (EBNF) špecifikácie formálnych gramatík.
4. Zostrojiť formálnu gramatiku podľa špecifikácie jazyka.

6. týždeň: Konštrukcia jazykových procesorov. Lexikálna a syntaktická analýza.

1. Oboznámiť so špecifikáciou priority a asociativity operácií na úrovni syntaktického modelu jazyka.
2. Predstaviť základnú teóriu jazykových procesorov.
3. Konštruovať gramatiku aritmetických výrazov, implementovať ich lexikálny a syntaktický analyzátor a syntaxou riadenú interpretáciu.

7. týždeň: Tranformácie bezkontextových gramatík.

1. Oboznámiť sa s transformáciami bezkontextových gramatík.
2. Precvičiť si transformácie bezkontextových gramatík.
3. Návrh plne rekurzívneho syntaktického analyzátora a interpretera na základe tranformovanej gramatiky jazyka aritmetických výrazov.

8. týždeň: Zásobníkové automaty a LL(1) parsovanie. Nerekurzívna syntaktická analýza zhora nadol.

1. Definovať zásobníkový automat ako ekvivalentný spôsob určenia bezkontextového jazyka.
2. Uviesť základné pojmy analýzy bezkontextových gramatík. Množiny $\mathit{FIRST},$ $\mathit{FOLLOW},$ $\mathit{PREDICT}$ a definovať $LL(1)$ gramatiku.
3. Predstaviť princíp nerekurzívnej syntaktickej analýzy zhora nadol postavenej na zásobníkovom automate.
4. Implementovať syntaktický analyzátor jednoduchého jazyka aritmetických výrazov na báze zásobníkového automatu.

9. týždeň: Konzultácia zadaní. Opakovanie učiva.

1. Konzultácie zadaní.
2. Príprava na zápočtovú písomku B.

10. týždeň: Zápočtová písomka B.

1. Zápočtová písomka B.

11. týždeň: Konzultácia zadaní.

1. Konzultácia zadaní.

12. týždeň: Obhajoba zadania.

1. Obhajoba zadania.

13. týždeň: Kontextové a frázové jazyky. Turingové stroje.

1. Definovať pumpovaciu lemu pre bezkontextové jazyky a demoštrovať jej využitie pri dôkaze neprislúšnosti jazyka do triedy bezkontextových jazykov.
2. Osvojiť si princípy konštrukcie kontextových a frázových gramatík na báze riešenia reprezentatívnych príkladov.
3. Presne opísať Turingov stroj ako výpočtový model s konkrétnymi inštrukciami.
4. Navrhnúť a implementovať Turingov stroj pre konkrétny jazyk.

Zadania