# Zápočet Majerech 14.5.2012, 15:40

<{ForumPost(poster="gejlord", timestamp=2012-05-15 09:32:10)}>
1) Rozhodněte, zda nedeterministický dvoucestný konečný automat se dvěma kamínky rozpoznává stejné jazyky jako deterministický konečný automat (bez kamínků).  
2) Pro parametry $b_1, b_2 \in \mathbb{Z}, b_i > 1$ zařaďte do Chomského hierarchie následující jazyk:  
  
  $L_{b_1, b_2} = \{ w | w = u \Xi v \}$, kde $u$ interpretované v soustavě o základu $b_1$ je stejné číslo jako $v^R$ (pozpátku) interpretované v soustavě o základu $b_2$. Čísla neobsahují "úvodní nuly" (resp. "koncové nuly" v obráceném zápisu). $\Xi$ je oddělovač.  
  
3) Dodejte redukovaný konečný automat přijímající slova nad $\{a,b\}^*$ obsahující "abba" jako podslovo a neobsahující "baab" jako podslovo.  
4) Popište regulárním výrazem jazyk přijímaný automatem:

          | 0 | 1 |
    ---------------
    <-> A | C | B | 
        B | A | C |
        C | A | C |
    

(na tabuli byl automat nakreslen obrázkem, ale nevim, jak to sem zakreslit.)
<{/ForumPost}>