SADA ÚLOH NA CVIČENIE 4

1. Uveďte formálne, ako budú vyzerať (pri simulácií LBA kontextovou gramatikou) pravidlá ošetrujúce okraje vetnej formy. (T.j. pravidlá, v ktorých sa vyskytujú päťposchodové neterminály s centom alebo dolárom na vhodnom poschodí.)

2. Daná je bezkontextová gramatika G. Zostrojte k nej TS A, ktorý keď dostane na vstupe vetnú formu w gramatiky G, spočíta, koľko rôznych vetných foriem sa dá v G odvodiť z w na 1 krok, výsledok vypíše (v ľubovoľnej, napr. unárnej sústave) a akceptuje. Zamyslite sa, ako by ste zostrojili LBA riešiaci túto úlohu.

3. Ukážte, že ku každej kontextovej gramatike existuje ekvivalentná, v ktorej každé pravidlo má na ľavej strane iba neterminály. Na základe toho formálne ukážte, že kontextové jazyky sú uzavreté na zreťazenie a kladnú iteráciu.

4. Pomocou gramatík ukážte, že kontextové jazyky sú uzavreté na nevymazávajúcu bezkontextovú substitúciu. (Nevymazávajúca substitúcia je taká, že epsilon nepatrí do obrazu žiadneho písmena.)

5. Pomocou LBA ukážte, že rozšírené kontextové jazyky sú uzavreté na nevymazávajúci homomorfizmus.

6. Dané je LBA A. Dokážte, že L = {u |  existuje v, x;uvx patri do L(A) ; | u| = | v| = | x|} je rozšírený kontextový jazyk.

7. Ukážte, že rozšírené kontextové jazyky nie sú uzavreté na homomorfizmus. (Hint: Ku každému TS M existuje LBA A a homomorfizmus h také, že h(L(A)) = L(M). Prečo?)

8. (Ťažšie.) Rozhodnite, či existuje k také, že nasledovná veta platí: Ku každému LBA existuje ekvivalentný s najviac k stavmi.