# Vomlelová 2020

<{ForumPost(poster="spidoosho", timestamp=2020-06-26 10:46:09)}>
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á)

*Attachments:*

- *[Otazky-AaG.pdf](/Forum%20archiv/Attachments/7221_d9d9189132346489f28b3f3f5d6c1ee1)*
- *[aag_moodle_test.zip](/Forum%20archiv/Attachments/7221_78edd08269d2be8af5c44a71e963e8c2)*

<{/ForumPost}>