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ů).
Pro parametry {: alt="b_1, b_2 \in \mathbb{Z}, b_i > 1" type="image/"} zařaďte do Chomského hierarchie následující jazyk:
{: alt="L_{b_1, b_2} = { w | w = u \Xi v }" type="image/"}, kde {: alt="u" type="image/"} interpretované v soustavě o základu {: alt="b_1" type="image/"} je stejné číslo jako {: alt="v^R" type="image/"} (pozpátku) interpretované v soustavě o základu {: alt="b_2" type="image/"}. Čísla neobsahují "úvodní nuly" (resp. "koncové nuly" v obráceném zápisu). {: alt="\Xi" type="image/"} je oddělovač.
Dodejte redukovaný konečný automat přijímající slova nad {: alt="{a,b}^*" type="image/"} obsahující "abba" jako podslovo a neobsahující "baab" jako podslovo.
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.)