Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Determinismus a nedeterminismus

Definice (Nedeterministický konečný automat)

Nedeterministický konečný automat je pětice , kde je mn. stavů, abeceda, mn. konc. stavů, množina počátečních stavů a je přechodová funkce. Slovo je takovým automatem přijímáno, pokud existuje posloupnost stavů tak, že , , .

Poznámka

Pro každý nedeterministický konečný automat lze sestrojit deterministický kon. automat tak, že jimi přijímané jazyky jsou ekvivalentní (může to znamenat exponenciální nárůst počtu stavů).

Definice (Deterministický zásobníkový automat)

Deterministický zásobníkový automat je takové, že platí a navíc pokud pro nějaké je , pak je .

Poznámka

Deterministický zásobníkový automat je slabší než nedeterministický, rozpoznává deterministické bezkontextové jazyky koncovým stavem a bezprefixové bezkontextové jazyky prázdným zásobníkem (takové jazyky, kde ) - když se poprvé zásobník automatu vyprázdní, výpočet určitě končí.

Bezprefixové bezkontextové jazyky jsou vždy deterministické, opačně to neplatí. Deterministický bezkontextový jazyk lze na bezprefixový převést zřetězením s dalším symbolem, který není v původní abecedě.

Regulární jazyky a bezprefixové bezkontextové jazyky jsou neporovnatelné množiny.

Definice (Nedeterministický Turingův stroj)

Nedet. Turingův stroj je pětice , kde oproti deterministickým je . Přijímá slovo , pokud existuje nějaký výpočet tak, že .

Poznámka

Nedeterministické Turingovy stroje přijímají právě rekurzivně spočetné jazyky, tj. nejsou silnější než deterministické. Výpočty nedet. stroje lze totiž díky nekonečnosti pásky simulovat deterministickým (např. prohledáváním do šířky).

Definice (Lineárně omezený automat)

Lineárně omezený automat je nedeterministický Turingův stroj s omezenou páskou (např. symboly a , které nelze přepsat ani se dostat mimo jejich rozmezí). Slovo je přijímáno, pokud , kde . Prostor výpočtu je omezen délkou vstupního slova. Lineárně omezené automaty přijímají právě kontextové jazyky.

Poznámka (Rozhodnutelnost)

Turingův stroj může nepřijmout slovo buď skončením výpočtu v nekoncovém stavu, nebo pokud výpočet nikdy neskončí. Turingův stroj rozhoduje jazyk , když přijímá právě slova tohoto jazyka a pro libovolné slovo je jeho výpočet konečný. Takové jazyky se nazývají rekurzivní.

Problém zastavení výpočtu Turingova stroje je algoritmicky nerozhodnutelný (kvůli možnosti jeho simulace jiným Turingovým strojem). Pro bezkontextové jazyky je algoritmicky rozhodnutelné, zda dané slovo patří do jazyka. Pro bezkontextovou gramatiku nelze algoritmicky rozhodnout, zda . Pro dvě kontextové gramatiky je nerozhodnutelné, zda jejich jazyky mají neprázdný průnik.