SADA ÚLOH NA CVIČENIE 5

Definície:

Hovoríme, že DTS A počíta funkciu f (definovanú na prirodzených číslach), ak pre všetky n platí: Ak spustíme A na vstupe aⁿ, v konečnom čase skončí a na páske bude slovo a^f(n). Stroj počítajúci funkciu môže zapisovať blanky.

1. Dokážte, že trieda jazykov, pre ktoré existuje deterministický lineárne ohraničený automat, je uzavretá na komplement.

2. Daný je nedeterministický TS A. Zostrojte k nemu ekvivalentný, ktorý zastaví akonáhle dosiahne akceptačný stav a ktorého každý výpočet je buď akceptujúci, alebo nekonečný.

3. Dokážte pomocou deterministických TS, ktoré na každom vstupe zastavia, že trieda rekurzívnych jazykov je uzavretá na kladnú iteráciu (+). Fungovalo by vaše riešenie aj pre rekurzívne vyčísliteľné jazyky? Ak nie, dá sa upraviť, aby fungovalo?

4. Zostrojte DTS A, ktorý bude počítať funkciu f (n) = n² + 5n + 5.

5. Zostrojte DTS A, ktorý bude počítať funkciu f (n) = dolná celá časť z lg n. (lg n je dvojkový logaritmus z n)

6. Ukážte, že problém konečnosti regulárneho jazyka je rozhodnuteľný. (T.j. že existuje DTS A, ktorý na každom vstupe zastaví a akceptuje kódy takých deterministických konečných automatov, ktoré akceptujú konečný jazyk.)

7. Definujte (t.j. uveďte štandardné 4 definície) TS, ktorý bude pracovať na dvojrozmernej páske, po ktorej sa hlava môže hýbať 4 smermi. Neformálne porovnajte jeho silu so štandardným TS.

8. Zaraďte jazyk L = {u#v | u, v patrí do {a, b}^*  ;  u sa nerovná v} do Chomského hierarchie.