N-AP15

Zadání

Rekurzivní a rekurzivně spočetné jazyky. Turingovy stroje. Pojem nerozhodnutelnosti a částečné rozhodnutelnosti.

Rekurzivní a rekurzivně spočetné jazyky

Definice

Jazyk L \subseteq \Sigma^* nazýváme
  • rekurzivně spočetnýL = L(M) pro nějaký Turnigův stroj M
  • rekurzivníL = L(M) pro nějaký úplný Turnigův stroj M

Ke každému rekurzivnímu jazyku L existuje Turingův stroj, který ho rozhoduje, tj. výpočet na každém vstupním slovu je konečný. Rekurzivně spočetný jazyk musí splňovat slabší podmínku: musí pro něj existovat Turingův stroj, který ho akceptuje, tj. akceptuje každé slovo z L, ale výpočet na slovu nepatřícím do L může být bud’ zamítající, nebo nekonečný.
Mezi rekurzivní jazyky patří regulární, bezkontextové, kontextové jazyky a další jazyky, které splňují podmínku rekurzivního jazyka. Každý rekurzivní jazyk je i rekurzivně spočetný (opačně to neplatí). Rekurzivně spočetné jazyky se dají generovat gramatikami typu 0. Metodou diagonalizace se dá dokázat, že existuje jazyk, který není rekurzivně spočetný.

S rekurzivními a rekurzivně spočetnými množinami úzce souvisí rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy:

Problémy

Problém, kde se má určit, zda řetězec w má vlastnost P nazýváme:
  • rozhodnutelný – právě když množina všech řetězců, která má vlasnost P, je rekurzivní
  • nerozhodnutelný – právě když není rozhodnutelný
  • částečně rozhodnutelný – právě když množina všech řetězců, která má vlastnost P, je rekurzivně spočetná

Uzávěrové vlastnosti rekurzivních a rekurzivně spočetných jazyků

Věta

Třídy rekurzivních a rekurzivně spočetných jazyků jsou uzavřeny vzhledem k operacím \cup,\ \cap,\ \cdot,\ \ast

Důkaz pro sjednocení

Necht’ L1, L2 jsou jazyky akceptovány Turingovými stroji M1,M2 a mají disjunktní množiny stavů. Nedeterministický stroj M∪, akceptující L1∪L2, dostaneme sjednocením strojů M1 a M2. Stroj M∪ bude mít navíc nový počáteční stav a v prvním kroku výpočtu stroj M∪ nedeterministicky přejde bud’ do požátežního stavu stroje M1, nebo do počátečního stavu stroje M2. V druhém kroku simuluje výpočet zvoleného stroje.

Důkaz pro průnik

Stroj M∩, akceptující L1∩L2, bude mít pásku se třemi stopami. Na první stopě je zapsán vstupní řetěz a její obsah se v průběhu výpočtu nemění. Stroj M∩ okopíruje svůj vstup w na druhou stopu a na ní simuluje výpočet M1 na w. V případě, že M1 akceptoval, okopíruje vstup w na třetí stopu a na ní pak simuluje výpočet M2 na w. Jestliže M2 akceptoval, pak M∩ též akceptuje. Jinak zamítá.

Důkaz pro zřetězení

Nedeterministický stroj , akceptující L1·L2, bude mít pásku se třemi stopami. Na první stopě je zapsáno vstupní slovo. Stroj překopíruje nějaký (může být i prázdný) prefix vstupního slova na druhou stopu — délku prefixu určí nedeterministicky. Symboly, které byly okopírovány se na první stopě označkují. Na druhé stopě pak simuluje výpočet M1. V případě, že simulovaný výpočet skončí v akceptující konfiguraci, tak překopíruje na třetí stopu zbylou (neoznačkovanou) část vstupu a simuluje výpočet M2 na řetězu zapsaném na třetí stopě. akceptuje právě když M2 akceptuje.

Nedeterministický stroj M∗, akceptující L1, je zobecněním stroje .

Věta

Třída rekurzivních jazyků je uzavřena vzhledem k operaci komplementu.

Důkaz pro komplement

Necht’ L je jazyk akceptovaný úplným deterministickým Turingovym strojem TM. Stroj co–M, akceptující jazyk co–L, získáme tak, že všude v definici přechodové funkce δ zaměníme navzájem akceptující stav qaccept a zamítající stav qreject . Protože M je úplný, bude i co–M úplný.

Postova věta

Necht’ jazyk L i jeho komplement co–L jsou rekurzivně spočetné. Pak jazyky L a co–L jsou rekurzivní. Postova věta je známa i jako tvrzení: L je rekurzivní ⇔ L a co–L jsou rekurzivně spočetné 1).

Důkaz

Předpokládejme, že M1 a M2 jsou Turingovy stroje akceptující po řadě jazyky L a co–L. Sestrojíme Turingův stroj M, který bude na vstupu w současně simulovat výpočet M1 na w i výpočet M2 na w. Formálně, stroj M bude mít dvě stopy, jednu pro každý simulovaný výpočet. M střídavě simuluje jeden krok výpočtu stroje M1 (na první stopě) a jeden krok výpočtu stroje M2 (na druhé stopě). M akceptuje vstup, právě když ho akceptuje M1 a M zamítá vstup, právě když ho akceptuje M2. Protože každý řetěz w patří bud’ do jazyka L anebo do jazyka co–L, výpočet M se pro každý vstup zastaví. Proto L je rekurzivní.

Důsledkem Postovy věty je, že třída rekurzivně spočetných jazyků není uzavřená na komplement. Pokud by platil opak, třídy rekurzivních a rekurzivně spočetných jazyků by se rovnaly.

Turingovy stroje

Definice

Turingův stroj (TM) je 9-tice M = (Q,\ \Sigma,\ \Gamma,\ \triangleright,\ \sqcup,\ \delta,\ q_0,\ q_{accept},\ q_{reject}) kde:
  • Q je konečná množina stavů
  • \Sigma je konečná množina vstupních symbolů
  • \Gamma je konečná množina páskových (pracovních) symbolů, obsahující jako svou podmnožinu abecedu \Sigma
  • \triangleright \in \Gamma \setminus \Sigma je levá koncová značka
  • \sqcup \in \Gamma \setminus \Sigma je symbol označující prázdne políčko
  • \delta:\ (Q \setminus \{q_{accept},q_{reject}\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} je totální přechodová funkce
  • q_0 \in Q je počáteční stav
  • q_{accept} \in Q je akceptující stav
  • q_{reject} \in Q je zamietající stav

Turingův stroj má konečnou množinu stavů Q, pásku, která je rozdělena na jednotlivá políčka, a hlavu, která se může po pásce pohybovat doleva a doprava, číst a zapisovat symboly. Na každém políčku pásky je zapsán právě jeden z konečně mnoha páskových (pracovních) symbolů. Páska je jednosměrně nekonečná. Na nejlevějším (nultém) políčku je zapsán speciální symbol \triangleright\, označující levý konec pásky. Na začátku výpočtu je na prvním až n-tém, n ≥ 0, políčku pásky zapsán vstupní řetěz (vstupem tedy může být i prázdný řetěz). Ostatních nekonečně mnoho políček napravo od vstupu je prázdných — tuto skutečnost vyjádříme pomocí speciálního znaku \sqcup\. Výpočet začíná v počátečním stavu q0, přičemž hlava snímá nulté políčko obsahující levou koncovou značku \triangleright\. Krok výpočtu spočívá v tom, že stroj v závislosti na momentálním stavu a symbolu snímaném hlavou

  1. změní svůj stav (či přesněji může změnit),
  2. zapíše symbol na políčko snímané hlavou (čímž přepíše symbol, který tam byl zapsán předtím) a
  3. posune hlavu o jedno políčko doprava, nebo doleva.

Způsob, jakým se má změnit stav, přepsat symbol a posunout hlava, předepisuje přechodová funkce δ. Stroj akceptuje vstupní řetěz, právě když přejde do speciálního akceptujícího stavu qaccept. Stroj zamítá právě když přejde do speciálního zamítajícího stavu qreject. Na některých vstupech může výpočet běžet nekonečně dlouho, aniž by stroj vstupní slovo akceptoval, nebo zamítnul. V takovém případě říkáme, že stroj pro daný vstup cyklí.
Navíc požadujeme, aby Turingův stroj nikdy nepřepsal levou koncovou značku jiným symbolem a aby nikdy neposunul svou hlavu vlevo od políčka obsahujícího levou koncovou značku. Formálně, požadujeme aby pro každé q \in Q existoval stav p \in Q takový, že: \delta(q,\triangleright) = (p,\triangleright,R)

Pojem nerozhodnutelnosti a částečné rozhodnutelnosti

Problém, kdy se má určit, zda řetěz w má vlastnost P, nazýváme:

  • rozhodnutelný právě když množina všech řetězů majících vlastnost P je rekursivní, tj. existuje úplný Turingův stroj M, který akceptuje každý řetěz mající vlastnost P a zamítne každý řetěz, který tuto vlastnost nemá (M rozhoduje jazyk obsahující právě všechna ta slova, která mají vlastnost P);
  • nerozhodnutelný právˇe když není rozhodnutelný;
  • částečně rozhodnutelný (semirozhodnutelný) právě když množina všech řetězů majících vlastnost P je rekursivně spoěetná, tj. existuje Turingův stroj, který akceptuje každý řetěz mající vlastnost P (a zamítá anebo cyklí pro řetěz nemající vlastnost P).

Namísto ”problém určit, zda řetěz w má vlastnost P je rozhodnutelný (částečně rozhodnutelný)“ zkráceně říkáme, že vlastnost P je rozhodnutelná resp. že problém P je rozhodnutelný (částečně rozhodnutelný). Ačkoli vlastnost rekursivní resp. rekursivně spočetný vypovídá o množinách, zatímco rozhodnutelnost resp. semirozhodnutelnost je vlastnost problémů, jsou oba pojmy úzce spjaty.

Platí mezi nimi tato ekvivalence:
P je rozhodnutelný ⇔ jazyk {w | w má vlastnost P} je rekursivní
L je rekursivní ⇔ problém ”w?∈L“ je rozhodnutelný
P je semirozhodnutelný ⇔ jazyk {w | w má vlastnost P} je rekursivně spočetný
L je rekursivně spočetný ⇔ problém ”w?∈L“ je semirozhodnutelný

Předměty

IB102 Automaty a gramatiky
IB005 Formální jazyky a automaty

Vypracoval

Marek Menšík UČO 255679
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů. Z mé strany je tato otázka dokončena a případné chybějící věci a chyby mě můžete napsat na UČO mail nebo se registrujte a upravte je sami.

Z mě strany prozatím hotovo
Možná by se u nerozhodnutelných problémů dalo doplnit více věcí jako Postův korespondenční problém, diagonalizace a jiné.

1)
ne rekurzivní, ve skriptech na s. 123 je nejspíš chyba
You could leave a comment if you were logged in.
mgr-szz/ap-ap/15-obr.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0