Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Únia: Ak sú L1 a L2 rozhodné jazyky, potom je tiež rozhodná L1 ∪ L2.
* Vysvetlenie: Môžeme zostaviť Turingov stroj (TM), ktorý rozhoduje L1 ∪ L2. TM na vstupe „W“ simuluje TMS pre L1 a L2 postupne.
* Najprv simulujte TM pre L1. Ak to akceptuje, potom prijmite „w“.
* Ak TM pre L1 odmietne, potom simulujte TM pre L2. Ak to akceptuje, potom prijmite „w“.
* Ak TM pre L2 odmietne, odmietnuť „W“.
* Kľúčový bod: Pretože L1 a L2 sú rozhodné, ich príslušné TMS * vždy * zastavia (buď prijímajú alebo odmietajú). To zaisťuje, že sa naša TM rozhodná o odboroch vždy zastaví.
2. Križovatka: Ak sú L1 a L2 rozhodné jazyky, potom je tiež rozhodná L1 ∩ L2.
* Vysvetlenie: Podobne ako v únii, môžeme postaviť TM, ktorý rozhoduje L1 ∩ L2.
* Simulujte TM pre L1. Ak to odmietne, odmietnuť „W“.
* Ak TM pre L1 prijíma, potom simulujte TM pre L2. Ak to akceptuje, potom prijmite „w“.
* Ak TM pre L2 odmietne, odmietnuť „W“.
3. Doplnok: Ak je L rozhodovateľným jazykom, potom je tiež rozhodný aj L '(doplnok L).
* Vysvetlenie: Môžeme zostaviť TM pre L 'jednoduchým vymenením a odmietnutím stavov TM, ktoré rozhodujú L.
* Vzhľadom na TM pre L vytvorte nový TM, ktorý je identický, s výnimkou:ak pôvodný TM akceptuje, nový TM odmietne. Ak pôvodný TM odmietne, nový TM akceptuje.
* Kľúčový aspekt: Funguje to iba *, pretože pôvodný TM je rozhodujúci a vždy sa zastaví. Ak by pôvodný TM mohol slučku, potom by táto operácia neviedla k rozhodovateľovi doplnku.
4. Zreťazenie: Ak sú L1 a L2 rozhodné jazyky, potom je tiež rozhodná L1L2 (zreťazenie L1 a L2).
* Vysvetlenie:
* Pri vstupe `w` skúste všetky možné spôsoby rozdelenia` w` na dve časti, `x` a` y`, takže `w =xy`.
* Pre každé rozdelenie simulujte TM pre L1 na `X` a TM pre L2 na` y`.
* Ak TM pre L1 akceptuje `x` * a * pre L2 akceptuje` y`, potom prijmite `w`.
* Ak boli vyskúšané všetky možné rozdelenia a žiadne nespĺňajú vyššie uvedenú podmienku, potom odmietnuť `W`.
* Dôležité: Pretože L1 a L2 sú rozhodnuteľné, tieto simulácie sa vždy zastavia. Pretože skúšame všetky možné rozdelenia, celková TM sa tiež vždy zastaví.
5. Kleene Star: Ak je L rozhodovateľným jazykom, potom je tiež rozhodná L* (Kleene hviezda L).
* Vysvetlenie: Je to podobné ako zreťazenie, ale umožňujeme viacnásobné zreťazenia (vrátane nuly).
* Pri vstupe `w`, pre` i =0` až `| w |`:(kde `| w |` je dĺžka `w")
* Vyskúšajte všetky možné spôsoby, ako rozdeliť `w` na` i` časti, `x1, x2, ..., xi`, tak, že` w =x1x2 ... xi`.
* Pre každé rozdelenie simulujte TM pre L na každom `XJ`.
* Ak TM pre L akceptuje každý `xj` (pre všetkých` j` od 1 do `i`), potom prijmite` w ".
* Ak boli vyskúšané všetky možné hodnoty `i` a všetky možné rozdelenia a žiadne splnili vyššie uvedenú podmienku, potom odmietnuť` w`.
* Kľúčové informácie: Pretože dĺžka akéhokoľvek reťazca v L* nemôže byť väčšia ako dĺžka vstupu `W`, môžeme obmedziť počet rozdelení, ktoré musíme vyskúšať. Simulácia sa zastaví po zvážení všetkých možných rozdelení.
6. Zvrátenie: Ak je l rozhodovateľný jazyk, potom l
* Vysvetlenie: Zostavte TM, ktorý robí nasledujúce:
* Zmeňte vstupný reťazec `w` a získajte` w
r `.
* Simulujte TM pre l on `w
r
`.
* Ak TM pre L akceptuje `w
r
`, potom prijmite` w`. V opačnom prípade odmietnuť `W`.
7. Rozdiel: Ak sú L1 a L2 rozhodné jazyky, potom je tiež rozhodná L1 - L2. (L1 - L2 obsahuje všetky reťazce v L1, ktoré nie sú * v L2).
* Vysvetlenie: L1 - L2 =L1 ∩ L2 '. Pretože rozhodujúce jazyky sú uzavreté v rámci doplnku a križovatky, sú tiež zatvorené pod rozdielom.
8. Predpona: Ak je L rozhodovateľným jazykom, potom predpona (l) ={x | Pre niektorých y, xy ∈ L} je rozhodovateľný.
* Vysvetlenie:
* Pri vstupe `X`, pre všetky možné` y` tak, že `| xy | <=| x | + som_constant`, (kde `som_constant` je maximálna dĺžka reťazcov na testovanie),
* Simulujte TM pre l on `xy`
* Ak TM akceptuje, prijmite `x`
* Odmietnuť, ak žiadna z vyššie uvedených simulácií neakceptuje.
Prečo je zatvorenie dôležitý?
Vlastnosti uzavretia sú zásadné pre pochopenie sily a obmedzení formálnych jazykových tried. Vedieť, že trieda jazykov je uzavretá pri určitých operáciách, nám umožňuje:
* Zostavte zložitejšie jazyky: Pomocou týchto operácií môžeme kombinovať jednoduchšie rozhodné jazyky a byť istí, že výsledný jazyk je tiež rozhodujúci.
* dokázať jazykové vlastnosti: Vlastnosti uzavretia sa môžu použiť v indukčných dôkazoch na preukázanie toho, že daný jazyk patrí do konkrétnej triedy.
* Design Algoritms: Algoritmy, ktoré demonštrujú uzavretie, slúžia ako plány na implementáciu analyzátorov a rozpoznávateľov pre zložité jazyky.
* Pochopte hierarchiu Decidability: Pomáhajú objasniť vzťah medzi rôznymi jazykovými triedami (napr. Pravidelný, bez kontextu, rozhodovateľný, rozpoznateľný).
Stručne povedané, vlastnosti uzávierky rozhodných jazykov sú základným kameňom teórie počítača. Ukazujú, že rozhodné jazyky sú robustnou a dobre správanou triedou jazykov.