Zápočet Majerech 14.5.2012, 15:40

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.)