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ů

### Třídy automatů a gramatik

Definice (Konečný automat)

Konečný automat je pětice , kde je stavový prostor (množina všech možných stavů), je abeceda (množina symbolů), je přechodová funkce , je poč. stav a množina koncových stavů.

Definice

Slovo je posloupnost symbolů v abecedě . Jazyk je množina slov, tedy , kde je množina všech posloupností symbolů abecedy . je prázdná posloupnost symbolů. Rozšířená přechodová funkce je - tranzitivní uzávěr . Jazyk rozpoznávaný konečným automatem - regularní jazyk je . Pravá kongruence je taková relace ekvivalence na , že . Je konečného indexu, jestliže má konečný počet tříd.

Věta (Nerodova)

Jazyk nad konečnou abecedou je rozpoznatelný kon. automatem, právě když existuje pravá kongruence konečného indexu na tak, že je sjednocením jistých tříd rozkladu .

Věta (Pumping (iterační) lemma)

Pro jazyk rozpoznatelný kon. automatem existuje tak, že libovolné slovo lze psát jako , kde , a .

Definice

Dva automaty jsou ekvivalentní, jestliže přijímají stejný jazyk. Homomorfismus (isomorfismus) automatů je zobrazení, zachovávající poč. stav, přech. funkci i konc. stavy (+ prosté a na). Pokud existuje ismorfismus automatů , pak jsou tyto dva ekvivalentní (jen 1 implikace!). Dosažitelný stav - . Relace ekvivalence je automatovou kongruencí, pokud zachovává konc. stavy a přech. funkci. Ke každému automatu existuje redukt - ekvivaletní automat bez nedosažitelných a navzájem ekvivalentních stavů. Ten je určen jednoznačně pro daný jazyk (až na isomorfismus), proto lze zavést normovaný tvar.

Poznámka (Operace s jazyky)

S jazyky lze provádět množinové operace ( ), rozdíl ( ), doplněk ( ), dále zřetězení ( ), mocniny ( ), iterace ( ), otočení , levý (i pravý) kvocient ( ) a derivace (kvocienty podle jednoslovného jazyka). Třída jazyků rozpoznatelných konečnými automaty je na tyto operace uzavřená.

Definice (Regulární jazyky)

Třída reguláních jazyků nad abecedou je nejmenší třída, která obsahuje , obsahuje a je uzavřená na sjednocení, iteraci a zřetězení.

Věta (Kleenova)

Jazyk je regulární, právě když je rozpoznatelný konečným automatem.

Definice (Regulární výrazy)

Regulární výrazy nad abecedou jsou nejmenší množina slov v abecedě , která obsahuje výrazy a a obsahuje a je uzavřená na sjednocení (), zřetězení () a iterace (). Hodnota reg. výrazu je reg. jazyk , lze takto reprezentovat každý reg. jazyk.

Definice (Dvoucestné konečné automaty)

Dvoucestný konečný automat je pětice , kde oproti kon. automatu je (tj. pohyb čtecí hlavy). Přijímá slovo, pokud výpočet začal vlevo v poč. stavu a čtecí hlava opustila slovo vpravo v konc. stavu (mimo slovo končí výpočet okamžitě).

Poznámka

Jazyky přijímané dvoucestnými automaty jsou regulární - každý dvoucestný automat lze převést na (nedeterministický) konečný automat.

Definice (Zásobníkové automaty)

Zásobníkový automat je sedmice , kde proti konečným automatům je abeceda pro symboly na zásobníku, počáteční symbol na zásobníku a funkce instrukcí . Je z principu nedeterministický; vždy se nahrazuje vrchol zásobníku, nečte ale pokaždé vstupní symboly. Instrukci lze vykonat, pokud je automat ve stavu , na zásobníku je a na vstupu . Vykonání instrukce znamená změnu stavu, pokud , tak i posun čtecí hlavy a odebrání ze zásobníku, kam se vloží (prvním písmenem nahoru). Výpočet končí buď přečtením slova, nebo v případě, že pro danou situaci není definována instrukce (Situace zás. automatu je trojice , kde , je nepřečtený zbytek slova a celý zásobník ).

Přijímat slovo je možné buď koncovým stavem (slovo je přečteno a automat v konc. stavu), nebo zásobníkem (slovo je přečteno a zásobník prázdný - konc. stavy jsou v takovém případě nezajímavé - ).

Poznámka

Pro zás. automat přijímající konc. stavem vždy existuje ekvivalentní automat ( ) přijímající zásobníkem a naopak.

Věta

Každý bezkontextový jazyk je rozpoznáván zásobníkovým automatem, přijímajícím prázdným zásobníkem. Stejně pro každý zásobníkový automat existuje bezkontextová gramatika, která generuje jazyk jím přijímaný.

Poznámka (Vlastnosti bezkontextových gramatik)

Bezkontextová gramatika je redukovaná, pokud existuje terminální slovo tak, že a navíc existují slova tak, že . Ke každé bezkontextové gramatice lze sestrojit ekvivalentní redukovanou.

Pro každé terminální slovo v bezkontextové gramatice existují derivace, které se liší jen pořadím použití pravidel (a prohozením některých pravidel dostanu stejné terminální slovo), proto lze zavést levé (pravé) derivace - tj. kanonické derivace. Pokud , pak existuje i levá (pravá) derivace. Znázornění průběhu derivací je možné určit derivačním stromem - určuje jednoznačně pravou/levou derivaci.

Bezkontextová gramatika je víceznačná (nejednoznačná), pokud v ní existuje slovo, které má dvě různé levé derivace; jinak je jednoznačná. Jazyk je jednoznačný, pokud k němu existuje generující jednoznačná gramatika. Pokud je každá gramatika nějakého jazyka nejednoznačná, je tento podstatně nejednoznačný.

Definice (Greibachové normální forma)

Gramatika je v Greibachové normální formě, jsou-li všechna její pravidla ve tvaru , kde a . Ke každému bezkontextovému jazyku existuje gramatika v G. normální formě tak, že . Každou bezkontextovou gramatiku lze převést do G. normální formy.

Poznámka (Úpravy bezkontextových gramatik)

Spojením více pravidel ( se převede na ) dostanu ekvivalentní gramatiku. Stejně tak odstraněním levé rekurze (převod přes nový neterminál).

Definice (Chomského normální forma)

Pro gramatiku v Chomského normální formě jsou všechna pravidla tvaru nebo , kde , . Ke každému bezkontextovému jazyku existuje gramatika v Chomského normální formě tak, že

Poznámka (Vlastnosti třídy bezkontextových jazyků)

Třída bezkontextových jazyků je uzavřená na sjednocení, zrcadlení, řetězení, iteraci a pozitivní iteraci, substituci a homomorfismus, inverzní homomorfismus a kvocient s regulárním jazykem. Není uzavřená na průnik a doplněk.

Definice (Dyckův jazyk)

Dyckův jazyk je definován nad abecedou gramatikou

Je bezkontextový, popisuje správná uzávorkování a lze jím popisovat výpočty zásobníkových automatů, tedy i bezkontextové jazyky.

Definice (Turingův stroj)

Turingův stroj je pětice , kde je abeceda, obsahující symbol pro prázdné políčko, přechodová funkce popisuje změnu stavu, zápis na pásku a posun hlavy. Výpočet končí, není-li definována žádná instrukce (spec. platí pro ). Konfigurace Turingova stroje jsou údaje, popisující stav výpočtu - nejmenší souvislá část pásky, obsahující všechny neprázdné buňky a čtenou buňku, vnitřní stav a poloha hlavy. Krok výpočtu je pro část slova vlevo od akt. pozice na pásce, od čteného písmena dál a stav stroje. Výpočet je posloupnost kroků, slovo je přijímáno, pokud , . Jazyky (množiny slov bez ) přijímané Turingovými stroji jsou rekurzivně spočetné.

Věta

Každý jazyk typu 0 (s gramatikou s obecnými pravidly) je rekurzivně spočetný.