Ako je možné dokázať, že jazyk je rozhodujúci?

Aby ste dokázali, že jazyk L je rozhodujúci, musíte preukázať, že existuje Turingov stroj (alebo ekvivalentný výpočtový model), ktorý sa zastaví a prijíma reťazce v L a odmieta reťazce, ktoré nie sú v L. Existuje niekoľko spôsobov, ako to preukázať:

1. Konštrukcia Turingovho stroja (alebo algoritmu):

Toto je najpriamejší prístup. Výslovne opíšete Turingov stroj (alebo algoritmus na vysokej úrovni, ktorý sa dá ľahko preložiť do Turingovho stroja), ktorý rozhoduje o jazyku. Tento popis musí pokryť:

* Vstup: Ako Turingov stroj prijíma vstupný reťazec.

* uvádza: Rôzne stavy, v ktorých môže byť stroj.

* prechody: Ako sa stroj pohybuje medzi stavmi na základe aktuálneho stavu a symbolu čítaný z pásky.

* Prijatie/odmietnutie: Ako stroj signalizuje akceptáciu (napr. Zadanie stavu „akcept“ alebo odmietnutie (napr. Zadanie „odmietnutia“ štátu).

* Zastavenie: Je dôležité, že musíte preukázať, že stroj * vždy * sa zastaví, bez ohľadu na to, či je vstupný reťazec v L alebo nie. Toto je najnáročnejšia časť.

Príklad: Zvážte jazyk l ={w | w je palindróm}. Môžeme opísať Turingov stroj, ktorý:

1. Skenuje vstupnú pásku zľava doprava a označte prvý a posledný symbol.

2. Pohybuje markery o krok dovnútra z oboch koncov.

3. Opakuje krok 2, kým sa stretávajú buď markery (reťazec je palindróm) alebo značky kríž (reťazec nie je palindróm).

4. Prijíma, či sa značky stretnú a odmietajú, ak prechádzajú.

Tento stroj sa vždy zastaví, čo dokazuje, že L je rozhodovateľný.

2. Redukcia na známy rozhodujúci jazyk:

Ak dokážete ukázať, že váš jazyk L je možné zredukovať na známy rozhodujúci jazyk L ', dokazuje sa, že l je tiež rozhodovateľný. Redukcia je vypočítateľná funkcia F tak, že:

* x ∈ L, ak a iba v prípade, že f (x) ∈ L '

Ak máte algoritmus na rozhodnutie L ', môžete ho použiť na rozhodnutie L najskôr použitím redukcie f. Pretože f a algoritmus pre l 'sú vypočítateľné, kombinovaný proces je tiež vypočítateľný, čím sa rozhoduje L.

Príklad: Nech l je jazykom reťazcov predstavujúcich platné aritmetické výrazy. Môžeme zredukovať L na gramatický jazyk bez kontextu (CFG) L ', ktorý je rozhodovateľný (existujú algoritmy analýzy pre CFG). Zníženie by zahŕňalo transformáciu aritmetického expresného reťazca na analyzný strom podľa gramatiky. Ak transformácia uspeje a vygeneruje sa platný strom analýzy, reťazec je v L; Inak to tak nie je.

3. Pomocou vlastností uzávierok rozhodných jazykov:

Rozhodnuteľné jazyky sú uzavreté pri určitých operáciách, ako sú únia, križovatka, zreťazenie, Kleene Star a doplnok. Ak dokážete vyjadriť svoj jazyk L pomocou týchto operácií v známych rozhodovateľných jazykoch, potom je L rozhodovateľný.

Príklad: Ak sú L1 a L2 rozhodné, L1 ∪ L2 je tiež rozhodovateľný. L1 ∪ L2 môžete rozhodnúť spustením rozhodovacích algoritmov pre L1 a L2 na vstupnom reťazci; Ak buď akceptuje, únia akceptuje.

v súhrne: Ukázalo sa, že deaktivovateľnosť sa scvrkáva k tomu, že ukazuje, že existuje deterministický algoritmus (alebo Turing Machine), ktorý vždy zastaví a správne klasifikuje každý vstupný reťazec ako patriaci k jazyku alebo nie. Metóda, ktorú si vyberiete, závisí od konkrétneho jazyka a vašej intuície o jeho vlastnostiach. Najbežnejším prístupom je priamy výstavba Turingovho stroja alebo algoritmu, ale redukcie a uzatváranie vlastností sú výkonné nástroje pre zložitejšie jazyky.

• Predchádzajúca strana: Aké sú príklady Turingovcov rozpoznateľných jazykov a ako sa líšia od iných typov jazykov? 
• Ďalšia strana: Ako sa dá použiť čerpacia lemma na preukázanie toho, že nasledujúce jazyky nie sú kontextové?