Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. zastavuje na všetkých vstupoch: TM musí nakoniec dosiahnuť akceptovaný stav alebo stav odmietnutia bez ohľadu na vstupný reťazec. Nemôže navždy slučku.
2. prijíma reťazce v jazyku l: Ak je reťazec `w` v L, TM sa zastaví v akceptovanom stave.
3. Odmieta reťazce nie v jazyku l: Ak reťazec `w` nie je v L, TM sa zastaví v stave odmietnutia.
Inými slovami, rozhodujúci jazyk má Turingov stroj, ktorý pôsobí ako dokonalý tester členstva:vždy dáva odpoveď „áno“ alebo „nie“ a vždy tak robí za konečnú dobu.
Tu je rozpis spoločných techník a úvah:
1. Konštrukcia Turingovho stroja (TM) Popis:
* Popis na vysokej úrovni: Začnite s jasným, čitateľným popisom algoritmu TM. To by malo vysvetliť logiku a kroky, ktoré sa týkajú spracovania vstupu. Myslite na to ako na pseudoCode.
* Implementačný popis (voliteľné): Môžete * poskytnúť popis na nižšej úrovni, ktorý špecifikuje stavy, funkciu prechodu, pásku abecedy atď. Toto je často únavné a nevyžadujú sa, pokiaľ o to výslovne požiada, alebo ak je algoritmus veľmi jemný a vyžaduje presnú definíciu. Najskôr sa zamerajte na popis na vysokej úrovni.
* Clarity je kľúč: Najdôležitejšie je, že váš popis je zrozumiteľný a presvedčivý. Slabý napísaný popis na vysokej úrovni môže byť ťažšie porozumieť ako dobre napísaný formálny opis.
2. Všeobecné stratégie na navrhovanie rozhodnutí:
* simulujte ďalšie stroje: Ak dokážete ukázať, že L sa môže rozhodnúť simuláciou iného rozhodujúceho jazyka (alebo viacerých takýchto jazykov), demonštrovali ste, že L je rozhodovateľný. Decidabilita je uzavretá pri mnohých operáciách (únia, priesečník, doplnok, zreťazenie, Kleene Star).
* Prevod na jednoduchší problém: Pokúste sa problém preformulovať na ekvivalentný, ale ľahšie vyriešiteľný problém.
* Zvážte základné prípady a rekurziu: Ak má problém rekurzívnu štruktúru, rekurzívny algoritmus je možné preložiť do rozhodcu Turingovho stroja. Uistite sa, že rekurzia je ohraničená, aby zaručila ukončenie.
* Vyhadzovacie vyhľadávanie: Ak je vstupný priestor konečný alebo môže byť ohraničený, môžete často použiť vyčerpávajúce vyhľadávanie na kontrolu všetkých možností. Kľúčovým bodom je, že vyhľadávanie musí byť zaručené, aby sa ukončilo.
* pákový efekt známe rozhodujúce jazyky: Budujte na základe vedomia, že určité jazyky sú už rozhodné. Napríklad bežné jazyky, jazyky bez kontextu a mnoho ďalších.
3. Techniky na demonštráciu ukončenia:
* počítanie: Ukážte, že algoritmus zahŕňa počítadlo, ktoré sa prísne zvyšuje alebo klesá smerom k viazaniu.
* klesajúca veľkosť: Ukážte, že každý krok algoritmu znižuje veľkosť problému, až kým nedosiahne triviálny základný prípad.
* Žiadne nekonečné slučky: Presvedčivo tvrdí, že algoritmus nemôže vstúpiť do nekonečnej slučky. To by mohlo zahŕňať preukázanie, že stroj vždy pohybuje páskou alebo že navštívené štáty sú v určitom období vždy zreteľné.
* simulačná dĺžka: Ak algoritmus simuluje ďalšie TM, vytvorte hornú hranicu počtu krokov, ktoré simulácia podniká. To často závisí od veľkosti vstupu.
4. Príklady a bežné scenáre:
* Pravidelné jazyky: Ak chcete ukázať pravidelný jazyk, je rozhodujúci, poskytnite jazyk DFA. TM môže simulovať DFA a zastaviť sa v stave akceptovaného alebo odmietnutia na základe konečného stavu DFA.
* Kontextové jazyky: Použite algoritmus CYK alebo podobný analytický algoritmus. Tieto algoritmy majú konečný beh.
* Nepreplateľnosť: Pochopte problém s zastavením. Nemôžete * rozhodnúť, či sa ľubovoľný Turingov stroj zastaví na ľubovoľnom vstupe. Ak dokážete znížiť problém s zastavením na váš problém, ukázali ste, že váš problém je nerozhodnuteľný (nie je možné).
* Prázdne testovanie: Zobrazenie jazyka je * prázdne * (neobsahuje žiadne reťazce) je niekedy jednoduchšie, ako ukazovať, že je rozhodovateľný. Napríklad jazyk Turingovho stroja je * nie * rozhodujúci. Avšak vzhľadom na DFA alebo CFG, určovanie, či jazyk, ktorý predstavuje, je prázdny * je * rozhodujúci.
5. Čo robiť:
* Nehlásite iba to, že je to vyhýbateľné bez odôvodnenia. Musíte uviesť primeraný argument, čo zvyčajne znamená opis algoritmu.
* Neposkytujte TM, že * iba * prijíma reťazce v jazyku. Musí tiež * odmietnuť * reťazce * nie * v jazyku a musí sa zastaviť.
* Neposkytujte algoritmus, ktorý by * mohol * zastaviť, ale má potenciál navždy slučku. Rozhodca * musí * zastaviť.
* Nezaujímajte rozhodnuteľnosť s rozpoznateľnosťou. Rozoznateľný jazyk vyžaduje iba TM, aby sa zastavil a akceptoval, ak je vstup v jazyku. Ak vstup nie je v jazyku, môže navždy slučky. Rozhodnuteľné jazyky sú vždy rozpoznateľné, ale konverzácia nie je pravdivá.
* Nesnažte sa poskytnúť „dôkaz pred príkladom“. Ukazujú, že konkrétny vstup je akceptovaný alebo zamietnutý, nedokáže nič o rozhodovaní jazyka.
Príklad 1:a ={0
n
1
* Popis na vysokej úrovni:
1. Naskenujte vstupný reťazec, aby ste sa uistili, že pozostáva iba z 0 s nasledovaným 1s. Ak nie, odmietnuť.
2. Aj keď zostávajú 0 a 1S:
* Prejdite na ľavú časť 0.
* Prejdite z ľavého najviac 1.
3. Ak zostávajú žiadne 0s a č. 1s, prijmite.
4. Ak zostane iba 0 s alebo iba 1, odmietnuť.
* Odôvodnenie: Tento algoritmus sa zastaví pre všetky vstupy. Kroky 1 a 3/4 ukončujú kontroly. Krok 2 prechádza z jedného 0 a jeden 1 v každej iterácii. Počet 0 s a 1S je konečný, takže slučka sa skončí. Ak bol počet 0 a 1 s rovnaký, akceptujeme. Inak odmietame.
Príklad 2:Je vzhľadom na DFA D, je jeho jazyk L (d) prázdny? A
* Popis na vysokej úrovni:
1. Označte štartovací stav D.
2. Opakujte, až kým sa žiadne nové štáty nezoznámili:
* Označte akýkoľvek štát, ktorý sa dá dosiahnuť z aktuálne označeného štátu sledovaním šípky v D.
3. Ak je nejaký akceptovaný stav D označený, odmietnuť.
4. Inak akceptujte.
* Odôvodnenie: Tento algoritmus sa zastaví. Krok 2 skúma všetky možné dosiahnuteľné stavy. Počet štátov v D je konečný, takže slučka sa skončí. Ak dokážeme dosiahnuť prijímajúci stav, jazyk nie je prázdny a odmietame. Inak je a my prijímame. Všimnite si, že „D` je zaručená, že bude DFA za predpokladu, a má teda konečné stavy.
Dodržiavaním týchto stratégií a pochopením vlastností Turingov a rozhodných jazykov môžete efektívne preukázať, že jazyk je rozhodujúci. Nezabudnite sa sústrediť na jasný a presvedčivý popis algoritmu a zvukový argument pre jeho ukončenie a správnosť.