SADA ÚLOH NA CVIČENIE 2



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

Ak sú všetky jazyky Lx regulárne (bezkontextové, ...), hovoríme, že substitúcia je regulárna (bezkontextová, ...)



  1. Nech L1, L2 sú rekurzívne vyčísliteľné jazyky, pričom ich zjednotenie aj prienik sú rekurzívne jazyky. Potom aj L1, L2 sú rekurzívne. Dokážte alebo vyvráťte.

  2. Zodpovedzte aspoň 2 otázky:
    a) Je rozhodnuteľné, či daný det. konečný automat A akceptuje slovo, ktorého dĺžka je mocnina 2?
    b) Je rozhodnuteľné, či daný LBA A akceptuje dané slovo w?
    c) Je rozhodnuteľné, či daný TS A akceptuje prázdne slovo?

  3. Zvoľte si netriviálny (najlepšie náhodný) deterministický konečný automat s aspoň 4 stavmi. Postupom z dôkazu Kleeneho vety zostrojte jazyk, ktorý tento automat akceptuje. Zapíšte ho ako regulárny výraz.

  4. Zostrojte čo najjednoduchší príklad relácie na {a, b}*, ktorá bude:
    a) reláciou ekvivalencie konečného indexu, ale nie sprava invariantná
    b) sprava invariantnou reláciou, ktorá nebude reláciou ekvivalencie
    c) sprava invariantnou reláciou ekvivalencie, ale nie konečného indexu
    d) to isté ako c), ale navyše musí byť zjednotením konečne veľa jej tried ekvivalencie jazyk, ktorý nebude ani bezkontextový
    Ak máte dojem, že niektorá podúloha nemá riešenie, zdôvodnite.

  5. Z regulárneho jazyka kontextovou (nevymazávajúcou) substitúciou dostaneme kontextový jazyk. Dokážte pomocou LBA. (Uveďte aj delta-funkciu.)

  6. Nech P je jazyk nad abecedou {0, ..., 9, + }, pričom P obsahuje práve tie slová, ktoré zodpovedajú korektným matematickým výrazom s výsledkom 7. Nech Q je jazyk všetkých korektných výrazov nad abecedou {0, ..., 9, +, *, (, ) }. Existuje bezkontextová substitúcia S1 taká, že S1(P) = Q? Existuje regulárna substitúcia S2 taká, že S2(Q) = P?

  7. Pomocou Myhill-Nerodovej vety ukážte, že jazyk {w | w = wR} nie je regulárny.

  8. Majme jazyk L = {w | w patrí do {a, b}*  ;  w neobsahuje podslovo aa}. Ako (presne!) vyzerá jemu prislúchajúca relácia RL z Myhill-Nerodovej vety?