Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky

Domáce Hardware Siete Programovanie Softvér Otázka Systémy

Čo je príklad rozhodujúceho jazyka?

Príkladom rozhodujúceho jazyka je jazyk `a ={ | M je dfa, ktorá akceptuje w} `. Inými slovami, jazyk pozostáva z párov deterministického konečného automatu (DFA) kódovaných ako reťazec a reťazca `w`, takže DFA akceptuje reťazec` w`.

Preto je to rozhodné a ako o tom môže Turingov stroj rozhodnúť:

Decidability: Jazyk je rozhodovateľný, ak existuje Turingov stroj, ktorý sa zastaví pri každom vstupe a prijíma vstup, ak je v jazyku a odmietne ho, ak nie.

Turing Machine Deaktor: Môžeme zostaviť Turingov stroj `d`, ktorý rozhoduje` a` takto:

1. Vstup: `D` berie ako vstup` `, kde` m` je kódovanie dfa a `w` je reťazec.

2. simulácia: `D` simuluje dfa` m` na vstupnom reťazci `w`. Je to možné, pretože `d` dokáže sledovať súčasný stav` m` a aktuálny symbol čítať z `w`. Simulácia pokračuje takto:

* Začnite `m` vo svojom počiatočnom stave.

* Pre každý symbol v `w`, prechod` m` do ďalšieho stavu podľa jeho prechodnej funkcie.

3. Prijať/odmietnuť:

* Ak `m` končí v stave akceptovania po prečítaní celého reťazca` w`, potom `d` akceptuje` `.

* Ak `M` končí v stave neúcty po prečítaní celého reťazca` w`, potom `d` odmietne` `.

Prečo to funguje:

* dfas vždy zastavte: DFA, podľa definície, spracováva každý vstupný symbol presne raz a potom sa zastaví. Nemajú žiadne nekonečné slučky ani nedefinované správanie.

* Simulácia je možná: Turingový stroj môže ľahko simulovať deterministické správanie DFA, pretože má dostatok pamäte a ovládania na sledovanie stavu a vstupnej polohy DFA.

* Zastavenie: Turing stroj `d` sa vždy zastaví, pretože simulácia DFA sa vždy zastaví.

* správnosť: `D` presne prijíma reťazce` `kde` m` akceptuje `w`, a presne odmieta reťazce` `kde` m` neakceptuje * w`.

formálny dôkaz (náčrt):

Aby ste dôsledne dokázali rozhodnosť, musíte:

1. formálne definujte kódovanie: Zadajte, ako sú DFA `M` a reťazec` W` znázornené ako reťazce vo vstupnej abecede Turingovho stroja `D`.

2. Uveďte stavový diagram alebo formálny opis prechodov `d`.

3. dokázať správnosť: Ukážte, že ak `` je v jazyku `a`, potom to` d` akceptuje, a ak `` nie je * v jazyku `a`, potom ho odmietne.

4. dokazujte zastavenie: Ukážte, že `d` vždy sa zastavuje pri akomkoľvek vstupe.

v súhrne: Pretože dokážeme postaviť Turingov stroj, ktorý sa vždy zastaví a správne prijíma alebo odmieta na základe toho, či daný DFA akceptuje daný reťazec, jazyk „A` je rozhodovateľný. Toto je základný a dôležitý príklad v teórii výpočtu.

Najnovšie články

Copyright © počítačové znalosti Všetky práva vyhradené