Obsah

IN12 Turingovy stroje a jazyky typu 0
Diskuze

IN12 Turingovy stroje a jazyky typu 0

(definice, vztah ke gramatikám Chomského hierarchie, rekurzivní a rekurzivně spočetné jazyky, uzávěrové vlastnosti)

Vypracovanie

Definícia

Turingov stroj

Turingov stroj (TM) je 9-tica $M = (Q,\ \Sigma,\ \Gamma,\ \triangleright,\ \sqcup,\ \delta,\ q_0,\ q_{accept},\ q_{reject})$ kde:

$Q$ je konečná množina stavov

$\Sigma$ je konečná množina vstupných symbolov

$\Gamma$ je konečná množina páskových (pracovných) symbolov, obsahujúca ako svoju podmnožinu abecedu $\Sigma$

$\triangleright \in \Gamma \setminus \Sigma$ je ľavá koncová značka

$\sqcup \in \Gamma \setminus \Sigma$ je symbol označujúci prázdne políčko

$\delta:\ (Q \setminus \{q_{accept},q_{reject}\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ je totálna prechodová funkcia

$q_0 \in Q$ je počiatočný stav

$q_{accept} \in Q$ je akceptujúci stav

$q_{reject} \in Q$ je zamietajúci stav

Naviac požadujeme, aby Turingov stroj nikdy neprepísal svoju ľavú koncovú značku iným symbolom a aby nikdy neposunul svoju hlavu vľavo od políčka obsahujúceho ľavú koncovú značku. Formálne, požadujeme aby pre každé $q \in Q$ existoval stav $p \in Q$ , taký že:
$\delta(q,\triangleright) = (p,\triangleright,R)$ Množina stavov spolu s prechodovou funkciou sa niekedy súhrnne označuje ako riadiacia jednotka Turingovho stroja.

Neformálny popis

Turingov stroj má konečnú množinu stavov Q, pásku, ktorá je rozdelená na jednotlivé políčka, a hlavu, ktorá sa môže po páske pohybovať doľava a doprava, čítať a zapisovať symboly. Na každom políčku pásky je zapísaný práve jeden z konečne mnoho páskových (pracovných) symbolov.
Páska je jednosmerne nekonečná. Na najľavejšom políčku je zapísaný symbol ľavého konca pásky $\triangleright$ . Na začiatku výpočtu je na prvom až n-tom ( $n \geq 0$ ) políčku pásky zapísaný vstupný reťazec. Ostatných nekonečne mnoho políčok napravo od vstupu je prázdnych (znak $\sqcup$ ).
Výpočet začína v počiatočnom stave $q_0$ , pričom hlava sníma nulté políčko obsahujúce značku $\triangleright$ . Krok výpočtu spočína v tom, že stroj v závislosti na momentálnom stave a symbolu snímaného hlavou:

zmení svoj stav (resp. ho môže zmeniť)
zapíše symbol na políčko snímané hlavou (čím prepíše symbol, ktorý tam bol predtým)
posunie hlavu o jedno políčko doprava alebo doľava

Spôsob, akým sa má zmeniť stav, prepísať symbol a posunúť hlava, predpisuje prechodová funkcia $\delta$ . $\delta (q,a) = (p,X,R)$ teda znamená, že ak stroj v stave q sníma symbol a, tak prejde do stavu p, symbol a prepíše symbolom X a hlavu posunie o jedno políčko doprava (R - right, L - left). Stroj akceptuje vstupný reťazec, ak prejde do stavu $q_{accept}$ , zamieta, ak prejde do stavu $q_{reject}$ .
Na niektorých vstupoch môže stroj bežať nekonečne dlho bez toho, aby vstupné slovo akceptoval alebo zamietol - v tom prípade stroj cyklí. Turingov stroj sa nazýva úplný práve vtedy, keď pre každý vstup zastaví.

Jazyk akceptovaný TM

Jazyk akceptovaný Turingovým strojom M definujeme ako množinu reťazcov, ktoré M akceptuje:

$L(M) = \{w \in \Sigma^{*} \ |\ M\ akceptuje\ w\}$

Ak je M úpný, hovoríme, že jazyk L(M) je rozhodovaný strojom M alebo že stroj M rozhoduje jazyk L(M).

Príklad na TM

Zadanie: Navrhnete Turingov stroj rozhodujúci jazyk $L = \{a^n b^n c^n \ |\ n \geq 0\}$ , ktorý nie je bezkontextový.
Idea riešenia:¹⁾ Stroj najskôr posúva svoju hlavu až na koniec vstupného reťazca a kontroluje, či je zapísaný na páske v tvare $a^* b^* c^*$ . Pritom nemení obsah pásky (zapíše prečítaný symbol). Keď hlava prečíta prvé prázdne políčko, začne sa posúvať doľava až na ľavý koniec pásky. Nasleduje cyklus, v ktorom hlava „vymaže“ (prepíše symbolom X) jeden symbol a, jeden b a jeden c a vráti sa na ľavý koniec pásky. Ak vstupný reťazec patrí do jazyka L, stroj nakoniec vymaže na vstupnej páske všetky symboly a, b, c a akceptuje. V opačnom prípade zamietne.

Rekurzivne a rekurzivne spočetné jazyky

Definícia

Jazyk $L \subseteq \Sigma^*$ nazývame

rekurzívne spočetný práve vtedy, keď L = L(M) pre nejaký Turnigov stroj M
rekurzívny práve vtedy, keď L = L(M) pre nejaký úplný Turnigov stroj M

Ku každému rekurzívnemu jazyku L existuje Turingov stroj, ktorý ho rozhoduje. Rekurzívne spočetný jazyk musí splňovať slabšiu podmienku: musí existovať Turingov stroj, ktorý ho akceptuje, t.j. akceptuje každé slovo z L, ale výpočet na slove nepatriaceho L môže byť buď zamietajúci alebo nekonečný.
Medzi rekurzívne jazyky patria regulárne, bezkontextové, kontextové jazyky a ďalšie jazyky, ktoré spĺňajú podmienku rekurzívneho jazyka. Každý rekurzívny jazyk je aj rekurzívne spočetný (opačne to neplatí). Rekurzívne spočetné jazyky sa dajú generovať gramatikami typu 0. Metódou diagonalizácie sa dá dokázať, že existuje jazyk, ktorý nie je rekurzívne spočetný.

S rekurzívnymi a rekurzívne spočetnými množinami úzko súvisia rozhodnuteľné, nerozhodnuteľné a čiastočne rozhodnuteľné problémy:

Problémy

Problém, kde sa má určiť, či reťazec w má vlastnosť P nazývame:

rozhodnuteľný práve keď množina všetkých reťazcov, ktorá má vlastnosť P, je rekurzívna
nerozhodnuteľný práve keď nie je rozhodnuteľný
čiastočne rozhodnuteľný práve keď množina všetkých reťazcov, ktorá má vlastnosť P, je rekurzíve spočetná

Uzáverové vlastnosti

Triedy rekurzívnych a rekurzívne spočetných jazykov sú uzavrené vzhľadom na operácie $\cup,\ \cap,\ \cdot,\ \ast$

Nech $L_1, L_2$ sú jazyky akceptované Turingovými strojmi $M_1, M_2$ s disjunktými množinami stavov:

Nedeterminstický stroj $M_{\cup}$ akceptujúci $L_1 \cup L_2$ dostaneme zjednotením strojov $M_1, M_2$ . Stroj $M_{\cup}$ bude mať nový počiatočný stav a v prvom kroku výpočtu stroj nedeterministicky prejde buď do počiatočného stavu $M_1$ alebo $M_2$ . V druhom kroku simuluje výpočet zvoleného stroja.

Stroj $M_{\cap}$ akceptujúci $L_1 \cap L_2$ bude mať pásku s troma stopami. Na prvej je zapísaný vstupný reťazec a jej obsah sa v priebehu výpočtu nemení. Stroj $M_{\cap}$ okopíruje svoj vstup w na druhú stopu a simuluje na nej výpočet $M_1$ . Ak $M_1$ akceptoval, okopíruje vstup na tretiu stopu a na nej simuluje výpočet $M_2$ . Ak $M_2$ akceptuje, akceptuje aj $M_{\cap}$ , v iných prípadoch zamietne.

Nedeterministický stroj $M_{\circ}$ akceptujúci $L_1 \cdot L_2$ bude mať pásku s troma stopami. Na prvej stope je zapísané vstupné slovo. Stroj prekopíruje nejaký (môže byť aj prázdny) prefix vstupného slova na druhú stopu - dĺžku prefixu určí nedeterminsiticky. Okopírované symboly sa na prvej páske označia. Na druhej stope potom $M_{\circ}$ simuluje výpočet $M_1$ . Ak $M_1$ akceptuje, $M_{\circ}$ prekopíruje na tretiu stopu zvyšnú neoznačkovanú časť slova a simuluje na nej výpočet $M_2$ . $M_{\circ}$ akceptuje práve vtedy, keď $M_2$ akceptuje.

Nedeterministický stroj $M^*$ akceptujúci jazyk $L_1^*$ je zobecnením stroja $M_{\circ}$ .

Komplement

Trieda rekurzívnych jazykov je uzavretá vzhľadom k operácii komplementu.

Ak L je jazyk akceptovaný úplným TM, stroj akceptujúci co-L zosrojíme jednoducho tak, že v definícii prechodovej funkcie $\delta$ zameníme navzájom akceptujúci stav $q_{accept}$ a zamietajúci stav $q_{reject}$ .

Postova veta

Nech jazyk L i jeho komplement co-L sú rekurzívne spočetné. Potom jazyky L a co-L sú rekurzívne. Postova veta je známa aj ako tvrdenie:
L je rekurzívny $\Leftrightarrow$ L a co-L sú rekurzívne

Dôsledkom Postovej vety je, že trieda rekurzívne spočetných jazykov nie je uzavretá na komplement. Ak by platil opak, triedy rekurzívnych a rekurzívne spočetných jazykov by sa rovnali.

Vzťah TS ku gramatikám Chomského hierarchie

Veta 1.1

Triedy jazykov, ktoré sa dajú generovať gramatikami typu 0, resp. akceptovať Turingovými strojmi sú si rovné a tvoria práve triedu rekurzívne spočetných jazykov.

Dôkaz je možné nájsť v skriptách ²⁾.
Každý rekurzívný jazyk je možné rozhodovať nejakým úplným Turingovým strojom. Z toho bezprostredne vyplýva, že ku gramatikám typu 1-3 (kontextová, bezkontextová, regulárna) vždy existuje úplný Turingov stroj, ktorý rozhoduje jazyk generovaný danou gramatikou. Ku gramatike typu 0 existuje TS, ktorý akceptuje jazyk generovaný touto gramatikou.

Prevod gramatiky typu 0 na TS

Nech L je jazyk generovaný gramatikou G=(N, Σ, P, S) typu 0. Nedeterministický TS M akceptujúci jazyk L bude mať 2 stopy. Na prvej stope je zapísaný vstupný reťazec a behom výpočtu sa nemení. Na druhej stope simuluje M odvodenie v G a je na nej zapísaná (do daného okamihu vygenerovaná) vetná forma α gramatiky G. Na zaciatku je obsah druhej stopy S a M opakovane prevádza tieto kroky:

nedeterministicky vybere pozíciu i v reťazci α na druhej stope.
nedeterminsticky zvolí pravidlo β → γ gramatiky G
ak je β podreťazcom reťazcu α začínajúcim na pozícii i, nahradí β reťazcom γ (ak nie sú rovnako dlhé, tak zvyšok druhej pásky posunie doľava alebo doprava)
ak sa reťazec na 1.stope rovná reťazcu na 2.stope - akceptuje, inak pokračuje znova krokom 1.

Prevod TS na gramatiku typu 0

Odvodenie v gramatike musí nejakým spôsobom simulovať výpočet stroja M. V gramatike G vygenerujeme dve kópie slova w nad abecedou Σ a nad druhou z nich v každom kroku odvodenia simulujeme jeden krok výpočtu stroja M. Ak stroj M neakceptuje, odvodenie nikdy nepovedie k terminálnemu reťazcu. Pravidlá na tvorenie pravidiel gramatiky sú pomerne zložité, nájsť ich môžete v skriptách ³⁾

Predmety

* FI:IB005 Formální jazyky a automaty I (jaro 2006), prof. RNDr. Mojmír Křetínský, CSc.

Použitá literatúra

* Skriptá k IB005

Vypracoval

Dušan Katona, ICQ: 426 081 873
hotovo: <99%>
môžete kluďne niečo doplniť alebo opraviť

Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.

¹⁾

kompletné riešenie, skriptá FJA, str. 108

²⁾

skriptá FJA, str. 123-125

³⁾

skriptá FJA , str. 125