Zápočet Majerech 14.5.2012, 15:40

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

Zápočet Majerech 14.5.2012, 15:40

Příspěvek od gejlord »

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:

Kód: Vybrat vše

      | 0 | 1 |
---------------
<-> A | C | B | 
    B | A | C |
    C | A | C |
(na tabuli byl automat nakreslen obrázkem, ale nevim, jak to sem zakreslit.)
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“