Deterministické zásobníkové automaty
Definice 3.72. Řekneme, že PDA M = (Q, E, I\ 5, Z0,F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky:
1. pro všechna q £ Q a Z £ T platí:   kdykoliv 5(q,e,Z) ^ 0, pak
a, Z) = 0 pro všechna a G S;
2. pro žádné g G        G Ta a ESU {e} neobsahuje 5(q,a,Z) více než jeden prvek.
Řekneme, že L je deterministický bezkontextový jazyk (DCFL), právě když existuje DPDA Ai takový, že L = L(A4).
IB102 Automaty a gramatiky, 12.12.2011
1
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82. Třída DCFL je uzavřena na doplněk.
Intuice: DPDA má nad každým slovem právě jeden výpočet. Pro doplněk 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, 12.12.2011
2
Komplikace 2: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí e-kroky pod kterýmy zásobník neomezeně roste.
Řešení: s = \Q\    t = |T|
r = max{|7| | (j/,7) G       s, Z),        G Q, Z G T}
zásobník neomezeně roste při ^-krocích <^=> během posloupnosti í-kroků jeho délka vzroste o více než r - s -1
IB102 Automaty a gramatiky, 12.12.2011
3
Komplikace 3: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí e-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 — \T\
r = max{|7| | (j/,7) G 5(p, e,Z), p,pf' G Q, Ze T}
IB102 Automaty a gramatiky, 12.12.2011
4
Komplikace 4: DPDA dočte slovo, ale pak pod e-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, 12.12.2011
5
Průnik a sjednocení
Věta. Třída DCFL není uzavřena na průnik.
Důkaz. Li = {anbncm \ rn. n > 1} a L2 = {ambncrn \ m,n > 1} jsou DCFL, ale L\ n L2 = {an6ncn | n > 1} není ani bez kontextový. □
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 doplněk, neuzavřenosti na průnik a z De Morgánových pravidel:
L\ n Z/2 = co-(co-Z/i U co-Z/2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.) □
IB102 Automaty a gramatiky, 12.12.2011
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, 6}*} je CFL, ale není DCFL
IB102 Automaty a gramatiky, 12.12.2011
7
Aplikace (deterministických) bezkontextových jazyků
• syntaxe programovacích jazyků je definována pomocí CFG (dobře uzávorkované výrazy, //- 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(l) - Yacc, Bison, javacup LL(k) - JavaCC, ANTLR
IB102 Automaty a gramatiky, 12.12.2011
8
Turingův stroj - syntaxe
Definice. Turingův stroj (TM) je M = (Q, E, T, >, U, ô, q0, gacc, grej), kde
• Q je konečná množina, jejíž prvky nazýváme stavy,
• S je konečná množina, tzv. vstupní abeceda,
• T je konečná množina, tzv. pracovní abeceda, S C T,
• > G T \ S je levá koncová značka,
• U G T \ S je symbol označující prázdné políčko,
• ô : (Q \ {gacc, grej}) x T       Q x T x {L, R} je totální přechodová funkce,
• Qo £ Q Je počáteční stav,
• ?acc £ Q je akceptující stav,
• ?rej £ Q je zamítající stav.
IB102 Automaty a gramatiky, 12.12.2011
9
Dále požadujeme, aby pro každé q G Q existoval p G Q takový, že S(q,>) = (p, >,iž) (tj. > nelze přepsat ani posunout hlavu za okraj pásky).
Označení. UW = UUUUUU...
Definice. Konfigurace Turingova stroje je trojice (g, z, n) GQxjyLT y G T*} x N0, kde
• q je stav,
• y\Ju je obsah pásky,
• n značí pozici hlavy na pásce.
Počáteční konfigurace pro vstup w G S* je trojice (go, >w\JUJ,0). Akceptující konfigurace je každá trojice tvaru (gacc, z, n). Zamítající konfigurace je každá trojice tvaru (qTe^z,ri).
IB102 Automaty a gramatiky, 12.12.2011
10
Výpočet Turingova stroje
Označení. Pro libovolný nekonečný řetěz z nad I\ zn označuje n-tý symbol řetězu z (z$]e nejlevější symbol řetězu z). Dále s%(z) označuje řetěz vzniklý ze z nahrazením zn symbolem b.
Definice.   Na množině všech konfigurací stroje Ai definujeme binárni
relaci
M
(krok výpočtu) takto:
{p, z, n)
M
{q, s%(z),n + 1) pro ô(p, zn) = (q, b, R) {q, s%(z),n - 1)     pro 5{p, zn) = {q, b, L)
IB102 Automaty a gramatiky, 12.12.2011
11
Výpočet TM Ai na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací K0, Äi, ..kde K0 je počáteční konfigurace pro w 3 Kí \-tj-Kí+i pro všechna i > 0.
Stroj A4 akceptuje slovo w právě když výpočet A4 na w je konečný a jeho poslední konfigurace je akceptující.
Stroj .M zamítá slovo u> právě když výpočet A4 na u> je konečný a jeho poslední konfigurace je zamítající.
Stroj A4 pro vstup w cyklí právě když výpočet A4 na u> je nekonečný.
Jazyk akceptovaný TM      definujeme jako
L (M) = {w eYT \ M akceptuje w}.
IB102 Automaty a gramatiky, 12.12.2011
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, 12.12.2011
13
Úplný Turingův stroj a rekursivní jazyky
Definice. Turingův stroj se vstupní abecedou S se nazýva úplný, pokud každé w G S* bud akceptuje nebo zamítá.
Jazyk se nazývá rekursivní, pokud je akceptovaný nějakým úplným Tu ringovým strojem.
IB102 Automaty a gramatiky, 12.12.2011
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 = {Q \ Q je regulární gr. a L(Q) je konečný}.
Definice. Problém P je
• rozhodnutelný {w \ w má vlastnost P} je rekursivní
• nerozhodnutelný {u> | w má vlastnost P} není rekursivní
• částečně rozhodnutelný (semirozhodnutelný)
{w \w n\i vlastnost P} je rekursivně spočetná
IB102 Automaty a gramatiky, 12.12.2011
15
Přehled jazykových tříd
Jazyky	Gramatiky (typ)	Automaty
rekursivně spočetné rekursivní kontextové bezkontextové deterministické CFL regulární	frázové (0) kontextové (1) bezkontextové (2) regulární (3)	Turingovy stroje úplné Turingovy stroje lineárně ohraničené TM zásobníkové automaty deterministické PDA konečné automaty
Třída na nižším řádku je vždy vlastní podtřídou třídy na vyšším řádku.
IB102 Automaty a gramatiky, 12.12.2011
16