Vomlelová 2020

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

Vomlelová 2020

Příspěvek od spidoosho »

Zkouška se skládá ze dvou částí: online moodle test a ústní zkouška.

online moodle test
Test je složen z 12 otázek, které se typově ptají na znění definice a vět, vlastnosti určitých automatů a gramatik. Otázky jsou velice podobné minitestíkům, které jsou na moodlu. Pokud si projdete všechny minitestíky, tak pak je moodle test celkem jednoduchý. V příloze jsou otázky z moodle testu a všechny otázky z minitestíků.

ústní zkouška
Vytáhnete si jednu otázku na kterou máte 10-15 minut na přípravu a potom s vámi diskutuje řešení. Pokud nevíte, tak vám poradí/naznačí postup. Je velice na zkoušce velice hodná a milá.
Otázky, které jsem nashromáždil:
- doplněk v deterministickém CFL
- urči rozdíly mezi jazyky L1 = \{w2w| w \in \{0,1\}^*\} a L2 = \{w2w^R|w \in {0,1}^*\}
- urči rozdíly mezi jazyky L1 = \{ww^R| w \in \{0,1\}^*\} a L2 = \{w2w^R|w \in {0,1}^*\}
- zařaď jazyk L = \{0^n1^n0^n\} do Chomského hierarchie + gramatiku jazyka L + lemma o vkládání
- zařaď jazyk L = \{0^n1^n0^n\} do Chomského hierarchie + napiš k němu LBA + převod LBA do gramatiky
- převod kontextová gramatika - lineárně omezený TM
- bezkontextové jazyky - napiš vše co víš + důkaz věty, kterou vybrala

- uzávěrové vlastnosti CFL, sjednocení konkatenace iterace + důkaz pro homomorfizmus a inverzní homomorfizmus
- zařaď jazyk L = \{ww| w \in \{0,1\}^*\} do Chomského hierarchie + pumping lemma + příklad jazyka, který je pumpovatelný, ale není CFL
- porovnat nedeterministický zásobníkový automat s přijímacím stavem a s prázdným zásobníkem + PL pro CFL
- zařaď jazyky L1 = \{ww| w \in \{0,1\}^*\} a L2 = \{wXw|w \in {0,1}^*\}, kde X je pismeno, které nepatří do abecedy
- CF jazyky uzavřenost na sjednocení, průnik, doplněk
- Srovnat sílu DFA vs NFA
- pumping lemma pro regulární jazyky (znění + důkaz) + příklad pumpovatelného ale neregulárního jazyka a důkaz neregularity
- determinizace nedeterministického turingova stroje (tato otázka je nejspíše již vyřazená)
Přílohy
Otazky-AaG.pdf
otazky z minitestíků
(136.11 KiB) Staženo 317 x
aag_moodle_test.zip
(351.85 KiB) Staženo 284 x
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“