Deterministické zásobníkové automaty Definice 3.72. Řekneme, že PDA M = (Q, , , , q0, Z0, F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky: 1. pro všechna q Q a Z platí: kdykoliv (q, , Z) = , pak (q, a, Z) = pro všechna a ; 2. pro žádné q Q, Z a a {} neobsahuje (q, a, Z) více než jeden prvek. Řekneme, že L je deterministický bezkontextový jazyk (DCFL), právě když existuje DPDA M takový, že L = L(M). IB102 Automaty a gramatiky, 15. 12. 2008 1 Vlastnosti deterministických bezkontextových jazyků Věta 3.82. Třída DCFL je uzavřena na doplňek. Intuice: DPDA má nad každým slovem právě jeden výpočet. Pro doplňek stačí zaměnit koncové a nekoncové stavy. Komplikace 1: DPDA nemusí dočíst vstupní slovo do konce, protože se vyprázdní zásobník nebo přechod není definován. Řešení: IB102 Automaty a gramatiky, 15. 12. 2008 2 Komplikace 2: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí -kroky pod kterýmy zásobník neomezeně roste. Řešení: s = |Q| t = || r = max{|| | (p , ) (p, , Z), p, p Q, Z } zásobník neomezeně roste při -krocích během posloupnosti -kroků jeho délka vzroste o více než r s t IB102 Automaty a gramatiky, 15. 12. 2008 3 Komplikace 3: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí -kroky pod kterýmy zásobník neroste neomezeně, tj. po jistém počtu kroků se jeho obsah opakuje. Řešení: s = |Q| t = || r = max{|| | (p , ) (p, , Z), p, p Q, Z } IB102 Automaty a gramatiky, 15. 12. 2008 4 Komplikace 4: DPDA dočte slovo, ale pak pod -kroky prochází koncové i nekoncové stavy (tj. některá slova jsou akceptována původním DPDA i DPDA se zaměněnými koncovými stavy). Řešení: IB102 Automaty a gramatiky, 15. 12. 2008 5 Průnik a sjednocení Věta. Třída DCFL není uzavřena na průnik. Důkaz. L1 = {an bn cm | m, n 1} a L2 = {am bn cm | m, n 1} jsou DCFL, ale L1 L2 = {an bn cn | n 1} není ani bezkontextový. P Věta. Třída DCFL je uzavřena na průnik s regulárním jazykem. Věta. Třída DCFL není uzavřena na sjednocení. Důkaz. Plyne z uzavřenosti na doplňek, neuzavřenosti na průnik a z De Morganových pravidel: L1 L2 = co­(co­L1 co­L2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.) P IB102 Automaty a gramatiky, 15. 12. 2008 6 Vztah deterministických a nedeterministických CFL Věta. Třída DCFL tvoří vlastní podtřídu třídy bezkontextových jazyků. Zejména existují bezkontextové jazyky, které nejsou DCFL. Příklad. Jazyk co­{ww | w {a, b} } je CFL, ale není DCFL. IB102 Automaty a gramatiky, 15. 12. 2008 7 Aplikace (deterministických) bezkontextových jazyků * syntaxe programovacích jazyků je definována pomocí CFG (dobře uzávorkované výrazy, if - then - else konstrukty) * DTD (Document Type definition) umožňuje definovat bezkontexové jazyky - využití ve značkovacích jazycích (HTML, XML,. . . ) * nástroje pro tvorbu parserů/překladačů využívají různé algoritmy pro lineární deterministickou syntaktickou analýzu: LALR(1) - Yacc, Bison, javacup LL(k) - JavaCC, ANTLR IB102 Automaty a gramatiky, 15. 12. 2008 8 Turingův stroj ­ syntaxe Definice. Turingův stroj (TM) je M = (Q, , , , , , q0, qacc, qrej), kde * Q je konečná množina, jejíž prvky nazýváme stavy, * je konečná množina, tzv. vstupní abeceda, * je konečná množina, tzv. pracovní abeceda, , * je levá koncová značka, * je symbol označující prázdné políčko, * : (Q {qacc, qrej}) × Q × × {L, R} je totální přechodová funkce, * q0 Q je počáteční stav, * qacc Q je akceptující stav, * qrej Q je zamítající stav. IB102 Automaty a gramatiky, 15. 12. 2008 9 Dále požadujeme, aby pro každé q Q existoval p Q takový, že (q, ) = (p, , R) (tj. nelze přepsat ani posunout hlavu za okraj pásky). Označení. = . . . Definice. Konfigurace Turingova stroje je trojice (q, z, n) Q×{y | y } × N0, kde * q je stav, * y je obsah pásky, * n značí pozici hlavy na pásce. Počáteční konfigurace pro vstup w je trojice (q0, w , 0). Akceptující konfigurace je každá trojice tvaru (qacc, z, n). Zamítající konfigurace je každá trojice tvaru (qrej, z, n). IB102 Automaty a gramatiky, 15. 12. 2008 10 Výpočet Turingova stroje Označení. Pro libovolný nekonečný řetěz z nad , zn označuje n-tý symbol řetězu z (z0 je nejlevější symbol řetězu z). Dále sn b (z) označuje řetěz vzniklý ze z nahrazením zn symbolem b. Definice. Na množině všech konfigurací stroje M definujeme binární relaci | M (krok výpočtu) takto: (p, z, n) | M (q, sn b (z), n + 1) pro (p, zn) = (q, b, R) (q, sn b (z), n - 1) pro (p, zn) = (q, b, L) IB102 Automaty a gramatiky, 15. 12. 2008 11 Výpočet TM M na vstupu w je maximální (konečná nebo nekonečná) posloupnost konfigurací K0, K1, K2, . . ., kde K0 je počáteční konfigurace pro w a Ki | M Ki+i pro všechna i 0. Stroj M akceptuje slovo w právě když výpočet M na w je konečný a jeho poslední konfigurace je akceptující. Stroj M zamítá slovo w právě když výpočet M na w je konečný a jeho poslední konfigurace je zamítající. Stroj M pro vstup w cyklí právě když výpočet M na w je nekonečný. Jazyk akceptovaný TM M definujeme jako L(M) = {w | M akceptuje w}. IB102 Automaty a gramatiky, 15. 12. 2008 12 Ukázky Turingových strojů a vztah k jazykům typu 0 Simulátor TM: http://www.fi.muni.cz/xbarnat/tafj/turing/ Věta. Jazyk L je rekursivně spočetný (tj. generovaný gramatikou typu 0) L je akceptovaný nějakým Turingovým strojem. IB102 Automaty a gramatiky, 15. 12. 2008 13 Úplný Turingův stroj a rekursivní jazyky Definice. Turingův stroj se vstupní abecedou se nazývá úplný, pokud každé w buď akceptuje nebo zamítá. Jazyk se nazývá rekursivní, pokud je akceptovaný nějakým úplným Turingovým strojem. IB102 Automaty a gramatiky, 15. 12. 2008 14 Rozhodnutelné a nerozhodnutelné problémy Problém rozhodnout, zda dané w má vlastnost P ztotožníme s množinou {w | w má vlastnost P}. Příklad. Problém rozhodnout, zda daná regulární gramatika reprezentuje konečný jazyk = {G | G je regulární gr. a L(G) je konečný}. Definice. Problém P je * rozhodnutelný {w | w má vlastnost P} je rekursivní * nerozhodnutelný {w | w má vlastnost P} není rekursivní * částečně rozhodnutelný (semirozhodnutelný) {w | w má vlastnost P} je rekursivně spočetná IB102 Automaty a gramatiky, 15. 12. 2008 15 Přehled jazykových tříd Jazyky Gramatiky (typ) Automaty rekursivně spočetné frázové (0) Turingovy stroje rekursivní - úplné Turingovy stroje kontextové kontextové (1) lineárně ohraničené TM bezkontextové bezkontextové (2) zásobníkové automaty deterministické CFL - deterministické PDA regulární regulární (3) konečné automaty Třída na nižším rádku je vždy vlastní podtřídou třídy na vyšším řádku. IB102 Automaty a gramatiky, 15. 12. 2008 16