Séria domácich úloh na cvičenie 14

Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že L, L1, L2, atď. sú ľubovoľné jazyky a h je ľubovoľný homomorfizmus. Zjednotenie značíme u, prienik ^, doplnok C, a reverz R. Nerovnosť značíme !=.

    Majme orientovaný graf X s vrcholmi očíslovanými prirodzenými čislami, nech jeho (orientované) hrany sú (i1,j1), (i2,j2),...,(in,jn). Takýto graf budeme kódovať do nasledovného slova: 0i11j10i21j2... 0in1jn. Náš kód grafu X budeme značiť <X>.

    Všimnite si, že kód grafu nie je jednoznačne určený (poradie hrán) a že zakódovaním strácame informáciu o vrcholoch stupňa 0. Rozmyslite si, že sa dá navrhnúť kód grafu, riešiaci oba tieto problémy. My však budeme pracovať s tým kódom, ktorý sme si práve zadefinovali. Vo všetkých troch úlohách môžete predpokladať, že v grafe X neexistujú izolované vrcholy, t.j. číslo každého vrcholu sa v kóde grafu X vyskytuje.

  1. Zostrojte (det. alebo nedet.) TS pre jazyk LHAM={ <X> | X obsahuje Hamiltonovský cyklus }
  2. Zostrojte (det. alebo nedet.) TS pre jazyk LEULER={ <X> | X obsahuje Eulerovský ťah }
  3. Zostrojte (det. alebo nedet.) TS pre jazyk L12={ <X> | X obsahuje cestu z vrchola 1 do vrchola 2 }
  4. Zadefinujte (štandardné 4 definície) Turingov stroj, ktorý vie okrem pohybu hlavou vložiť na pásku pod hlavu nové políčko alebo odstrániť existujúce políčko spod hlavy. Porovnajte jeho silu so štandardným TS.
  5. Zadefinujte (štandardné 4 definície) Turingov stroj so diernou páskou. Takýto Turingov stroj pozná 2 špeciálne symboly - blank a dieru. Na páske môže na políčko s blankom zapísať ľubovoľný symbol z pracovnej abecedy. Na políčko so symbolom pracovnej abecedy môže zapísať iba ten istý symbol (t.j. nevie ho prepísať iným) alebo dieru. Na políčko s dierou už môže zapísať iba dieru. Porovnajte jeho silu so štandardným TS.
  6. Vytvorte bezkontextovú gramatiku G, ktorá generuje práve všetky regulárne výrazy.
  7. Nech L = { w | w patrí do {a,b}*, w obsahuje podslovo baba alebo #a(w)<=3 }. Napíšte regulárny výraz, ktorý popisuje jazyk L.
  8. Nech L = { w | w patrí do {a,b}*, #a(w) mod 3 = #b(w) mod 3 }. Napíšte regulárny výraz, ktorý popisuje jazyk L.
  9. Daný je DTS A1 taký, že L(A1)=L. Daný je DTS A2 taký, že L(A2)=LC. Detailne popíšte konštrukciu deterministického TS A, ktorý vždy zastaví, takého, že L(A)=L. Nie je potrebné uvádzať úplnú delta-funkciu.