Deterministické zásobníkové automaty
Definice 3.72. Rekneme, že PDA M = (Q, S, T,ô,q0,Z0,F) je deterministicky (DPDA), jestliže jsou splnený tyto podmínky:
1. pro všechna q G Q a Z G r platí:   kdykoliv ô (q, e, Z) = 0, pak ô (q, a, Z) = 0 pro všechna a G S;
2. pro žadne q G Q, Z G r a a G S U {e} neobsahuje ô (q,a, Z) více než jeden prvek.
Rekneme, že L je deterministicky bezkontextovy jazyk (DCFL), prave když existuje DPDA M takový, že L = L(M).
IB102 Automaty a gramatiky, 13.12.2010
1
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82. Třída DCFL je uzavřena na doplňek.
Intuice: DPDA ma nad kaZdým slovem prave jeden výpočet. Pro doplňek stačí zamenit koncove a nekoncove stavý.
Komplikace 1: DPDA nemusí dočíst vstupní slovo do konce, protoZe se výprazdn í zasobn ík nebo přechod nen í definovan.
ReSení:
IB102 Automaty a gramatiky, 13.12.2010
2
Komplikace 2: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustale provádí s-kroky pod kterýmy zásobník neomezené roste.
Rešení: s = |Q|    t = |r|
r = max{|71 | (p7,Y) G 5(p, s, Z), p, p7 G Q, Z G r}
žásobn ík neomežene roste pri s-kroc ích behem posloupnosti
s-krokU jeho delka vžroste o v íce než r • s • t
IB102 Automaty a gramatiky, 13.12.2010
3
Komplikace 3: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustale provádí e-kroky pod kterýmy zásobník neroste neomežene, tj. po jistem počtu krokU se jeho obsah opakuje.
Rešení: s = |Q|    t = |r|
r = max{|71 | (p7,7) G ô (p, e, Z), p, p7 G Q, Z G r}
IB102 Automaty a gramatiky, 13.12.2010
4
Komplikace 4: DPDA dočte slovo, ale pak pod £-kroky prochází koncové i nekoncove stavy (tj. některá slova jsou akceptována původním DPDA i DPDA se zamenenymi koncovými stavy).
Rešení:
IB102 Automaty a gramatiky, 13.12.2010
5
Průnik a sjednocení
Věta. Třída DCFL není uzavřena na průnik.
Důkaz. Li = {anbncm | m,n > 1} a L2 = {ambncm | m, n > 1} jsou DCFL, ale Li n L2 = {anbncn | n > 1} není ani bezkontextový. □
Věta. Třída DCFL je uzavřena na průnik s regularn ím jazykem.
Věta. Třída DCFL nen í uzavřena na sjednocen í.
Důkaz. Plýne z uzavřenosti na doplřek, neuzavřenosti na prunik a z De Morganových pravidel:
Li n L2 = co-(co-Li U co-L2) (Z uzavřenosti na sjednocen í bý plynula uzavřenost na prunik.) □
IB102 Automaty a gramatiky, 13.12.2010
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í bezkontextove jazyky, které nejsou DCFL.
Príklad. Jazyk co-{ww | w G (a, 6}*} je CFL, ale nen í DCFL.
IB102 Automaty a gramatiky, 13.12.2010
7
Aplikace (deterministických) bezkontextových jazyků
• syntaxe programovacích jazyků je definována pomocí CFG (dobre ůzavorkovane vyrazy, if - then - else konstrukty)
• DTD (Document Type definition) ůmoZňůje definovat bezkontexove jazyky - vyuziti ve znackovacích jazycích (HTML, XML,. . . )
• nastroje pro tvorbů parserů/prekladaců vyůzívají různe algoritmy pro linearní deterministickou syntaktickoů analyzů:
LALR(1) - Yacc, Bison, javacůp LL(k) - JavaCC, ANTLR
IB102 Aůtomaty a gramatiky, 13.12.2010
8
Turingův stroj - syntaxe
Definice. Turingův stroj (TM) je M = (Q, S, r, >, U, ô, qo, qacc, qrej),
kde
• Q je konecna mnoZina, jejíZ prvky nazyvame stavy,
• S je konecna mnoZina, tzv. vstupní abeceda,
• r je konecna mnoZina, tzv. pracovn í abeceda, S C r,
• > G r \ S je leva koncova znacka,
• U G r \ S je symbol oznacuj íc í prazdne pol ícko,
• ô : (Q \ {qacc, qrej}) x r ^ Q x r x {L, R} je totain í prechodova funkce,
• q0 G Q je pocatecn í stav,
• qacc G Q je akceptuj íc í stav,
• qrej G Q je zam ítaj íc í stav.
IB102 Automaty a gramatiky, 13. 12. 2010
9
Dale požadujeme, aby pro každe q G Q existoval p G Q takovy, že 5(q, >) = (p, >,R) (tj. > nelže prepsat ani posunout hlavu ža okraj pasky).
OznaCení. = UUUUUU ...
Definice. Konfigurace Turingova stroje je trojice (q,z,n) G Qx{yUu y G ľ*} x N0, kde
• q je stav,
• yje obsah pasky,
• n žnací požici hlavy na pasce.
PoCateCní konfigurace pro vstup w G S* je trojice (q0, >wU, 0). Akceptující konfigurace je každa trojice tvaru (qacc,z,n). Zam ítaj íc í konfigurace je každa trojice tvaru (qrej,z, n).
IB102 Automaty a gramatiky, 13. 12. 2010
10
Výpocet Tůringova stroje
Oznacení. Pro libovolný nekonecný řetez z nad r, zn oznacuje n-tý sýmbol řetezu z (z0 je nejlevejsí sýmbol retezu z). Dale (z) oznacuje řetez vzniklý ze z nahrazením zn sýmbolem b.
Definice. Na mnozine vsech konfigurací stroje M definujeme binarní relaci (krok výpočtu) takto:
(q,sn(z ),n + 1)
pro ô(p,zn) = (q,b,R)
M
(q,sn(z),n - 1)
pro ô(p,zn) = (q,b,L)
IB102 Automatý a gramatiký, 13. 12. 2010
11
Výpocet TM M na vstupu w je maximain í (konecna nebo nekonecna) posloupnost konfigurac í K0 , Ki,K2,kde K0 je počáteční konfigurace pro w a Ki \-j^-Ki+i pro všechna i > 0.
Stroj M akceptuje slovo w prave kdyz vypocet M na w je konecny a jeho posledn í konfigurace je akceptuj íc í.
Stroj M zamíta slovo w prave kdyz vypocet M na w je konecny a jeho posledn í konfigurace je zam ítaj íc í.
Stroj M pro vstup w cýkú prave kdyz vypocet M na w je nekonecny.
Jazýk akceptovaný TM M definujeme jako
L(M) = (w G S* | M akceptuje w}.
IB102 Automaty a gramatiky, 13. 12. 2010
12
Ukazky Turingových štrojů a vztah k jazykům typu 0
Simulator TM: http://www.fi.muni.čž/^xbarnat/tafj/turing/
Veta. Jažyk L je rekursivne spočetny (tj. generovany gramatikou typu 0) L je akčeptovany nejakym Turingovym strojem.
IB102 Automaty a gramatiky, 13. 12. 2010
13
r _
Uplný Turingův stroj a rekursivní jazýký
Definice. Turinguv stroj se vstupn í abecedou S se nazyva úplný, pokud kaZde w G S* bud akceptuje nebo zam íta.
Jazyk se nazyva rekursivní, pokud je akceptovany nejakym uplnym Turingovym strojem.
IB102 Automaty a gramatiky, 13. 12. 2010
14
Rozhodnutelné a nerozhodnutelné problémy
Problém rozhodnout, zda dané w ma vlastnost P ztotožn íme s množinou {w | w ma vlastnost P}.
Príklad. Problém rozhodnout, zda dana regularn í gramatika reprezentuje konečný jazyk = {G | G je regularn ígr. a L(G) je konečný}.
Definice. Problem P je
• rozhodnutelný {w | w ma vlastnost P} je rekursivn í
• nerozhodnutelny {w | w ma vlastnost P} nen í rekursivn í
• CasteCne rozhodnutelný (semirozhodnutelny)
{w | w ma vlastnost P} je rekursivne spočetna
IB102 Automaty a gramatiky, 13.12. 2010 15
Přehled jazykovych tříd
Jazyky	Gramatiky (typ)	Automaty
rekursivně spočetné rekursivní kontextové bezkontextové deterministické CFL regulární	frázové (0) kontextové (1) bez kontextové (2) regulární (3)	Turingovy stroje uplne Turingovy stroje linearne ohraniCene TM žasobníkove automaty deterministicke PDA koneCne automaty
Trída na nižsím radku je vždy vlastní podtrídou třídy na vyssím radku.
IB102 Automaty a gramatiky, 13. 12. 2010
16