SADA ÚLOH NA CVIČENIE 3



Definície:

Substitúcia je zobrazenie S, určené abecedou Sigma a jazykom Lx pre každé x zo Sigma. Obrazom slova w = w1w2...wn v substitúcií S bude jazyk S(w) = Lw1Lw2...Lwn. (Neformálne: Každé písmeno slova nahradíme nejakým slovom z príslušného jazyka, a to všetkými možnými spôsobmi.) Obraz jazyka L v substitúcií S bude jazyk S(L) =  Zjednotenie(w patrí do L)S(w).

Nech S je substitúcia. Potom inverzná substitúcia S-1 je nasledovné zobrazenie: Obrazom slova w bude jazyk S-1(w) = {u| w patrí do S(u)}. (Neformálne: je to jazyk tých slov u, ktorých obraz v S obsahuje w.) Obrazom jazyka L bude jazyk S-1(L) =  Zjednotenie(w patrí do L)S-1(w).

Ak sú všetky jazyky Lx regulárne (bezkontextové, ...), hovoríme, že substitúcia a príslušná inverzná substitúcia sú regulárne (bezkontextové, ...)



  1. Sú regulárne jazyky uzavreté na inverznú regulárnu substitúciu? Rozhodnite a dokážte.

  2. Nech L je ľubovoľný jazyk, S regulárna substitúcia. Porovnajte jazyky L, S(S-1(L)) a S-1(S(L)) (teda pre každú dvojicu rozhodnite, aký je medzi prísušnými jazykmi vzťah).

  3. Dokážte, že ku každému A-prekladaču existuje ekvivalentný, ktorý v každom kroku prečíta aj zapíše najviac 1 písmeno.

  4. Dokážte, že ku každému homomorfizmu h (zo slov nad Sigma1 do slov nad Sigma2) existujú A-prekladače A1, A2 také, že:
    - pre všetky jazyky L nad abecedou Sigma1 platí h(L) = A1(L)
    - pre všetky jazyky L nad abecedou Sigma2 platí h-1(L) = A2(L).
    Zdôvodnite, či analogické tvrdenie platí aj pre regulárne substitúcie.

  5. Dokážte, že ku každému regulárnemu jazyku R nad abecedou {a, b} existujú A-prekladače A1, A2, také, že pre všetky jazyky L nad abecedou {a, b} platí L prienik R = A1(L), L - R = A2(L).

  6. Zostrojte A-prekladač, ktorý preloží jazyk L1 dobre uzátvorkovaných výrazov nad abecedou { (,),[,] } na jazyk L2 = {w | #a(w) = #b(w)} alebo dokážte, že sa to nedá.

  7. Definujte TS so vstupnou páskou (len na čítanie) a k pracovnými páskami. Ukážte, že takýto TS je ekvivalentný so štandardným. (Nemusíte uvádzať kompletnú delta-funkciu stroja, stačí dostatočne detailný popis, ako ju zostrojiť.)

  8. Zostrojte TS, ktorý keď spustíme na slove #u#v#w#, tak:
    - ak u nie je podslovom w, neakceptuje
    - ak u je podslovom w, prepíše pásku tak, aby na konci ostalo na páske slovo #u#v#w'# (pričom w' vznikne z w tak, že niektorý výskyt slova u nahradíme slovom v) a akceptuje
    Váš TS môže zapisovať blanky.