Deterministické zásobníkové automaty
Definice 3.72. Řekneme, že PDA M = (Q, Z, r, 5, gb, Z0, F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky:
D pro všechna q e Q a Z e V platí:
kdykoliv 5(q, e, Z) 7^ 0, pak     a, Z) = 0 pro všechna a e Z
Q pro žádné qeQ, ZeVaaeTu{e} neobsahuje 5(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, 16.12.2019
1/16
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, 16.12.2019
2/16
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=\V\
r = max{|7| | (p', 7) G 5(p, e, Z), p,př eQ,Z e l~}
zásobník neomezeně roste při s-krocích <4=^> během posloupnosti č-kroků jeho délka vzroste o více než r>s-t
IB102 Automaty a gramatiky, 16.12.2019
3/16
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 = IQL   t = III
r = max{|7| | (př^) eô(p,e,Z), p,př e Q, Z eV}
IB102 Automaty a gramatiky, 16.12.2019
4/16
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, 16.12.2019
5/16
o ■
a sjednocení
Věta. Třída DCFL není uzavřena na průnik.
Důkaz. = {anbncm |m,n>1}aL2 = {ambncm {m^n^-i}jsou DCFL, ale L1 n L2 = {anbncn | n > 1} není ani bezkontextový.
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 Morganových pravidel:
L| n Z-2 = co-(co-Li u C0-/-2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.)
IB102 Automaty a gramatiky, 16.12.2019
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 e {a, £>}*} je CFL, ale není DCFL.
IB102 Automaty a gramatiky, 16.12.2019 7/16
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, 16.12.2019
8/16
Turingův stroj - syntaxe
Definice. (Deterministický) Turingův stroj (Turing Machine, TM) je
devítice M = (Q, Z, r, >, u, S, cfo, QaCc, Qrej), kde
■ Q je konečná množina, jejíž prvky nazýváme stavy,
■ Z je konečná množina, tzv. vstupní abeceda,
■ r je konečná množina, tzv. pracovní abeceda, Z c r,
■ > g r \ Z je levá koncová značka,
■ u g r \ Z je symbol označující prázdné políčko,
■ ô : (Q \ {Qacc, Qrej}) x ľ -> Q X ľ X {/_, f?}
je totální přechodová funkce,
■ Qo e Q je počáteční stav,
■ Qacc £ Qje akceptující stav,
■ Qrej g Q je zamítající stav, qacc ^ qrej.
IB102 Automaty a gramatiky, 16.12.2019 9/16
Dále požadujeme, aby pro každé qgQ \ {gacc, Qrej} existoval p e Q takový, že 8{q, >) = (p, >, R) (tj. > nelze přepsat ani posunout hlavu za okraj pásky).
Označení. uw = uuuuuu...
Definice. Konfigurace Turingova stroje je trojice
(g, z, rí) g Q x {yu^ | y g r*} x N0, kde
■ q je stav,
■ yuu je obsah pásky,
■ n značí pozici hlavy na pásce.
Počáteční konfigurace pro vstup w e Z* je trojice (g0, >wu^, 0). Akceptující konfigurace je každá trojice tvaru (Qacc, z, n). Zamítající konfigurace je každá trojice tvaru (grej, z, n).
IB102 Automaty a gramatiky, 16.12.2019
10/16
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 (z0 je 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 M definujeme binární
relaci krok výpočtu
M
takto:
(P, z, n)
M
<
(q, sg(z), n + 1) pro 5{p, zn) = (q, b, R) ^ (q, sg(z), n - 1)    pro č(p, zn) = (q, b, L)
IB102 Automaty a gramatiky, 16.12.2019
11/16
Výpočet TM M na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací K0, Kí, K2,..kde K0 je počáteční konfigurace
pro w a Kj      K/+1 pro všechna / > 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(A^) = {w g Z* | .M akceptuje w}.
IB102 Automaty a gramatiky, 16.12.2019
12/16
Ukázky Turingových strojů
Simulátor TM:
■ kdysi: http : / /www. f i . muni . cz/~xbarnat /taf j /turing/
■ nově: http://www.fi.muni.cz/~xjochecl/turing/
IB102 Automaty a gramatiky, 16.12.2019
13/16
Turingovy stroje a třídy jazyků
Věta. Jazyk L je rekursivně spočetný (tj. generovaný gramatikou typu 0) <=^> L je akceptovaný nějakým Turingovým strojem.
Důkaz. Neuveden. □
Definice. Turingův stroj se vstupní abecedou Z se nazývá úplný, je-li každý jeho výpočet konečný (akceptující nebo zamítající).
Jazyk se nazývá rekursivní, pokud je akceptovaný nějakým úplným Turingovým strojem.
IB102 Automaty a gramatiky, 16.12.2019
14/16
Rozhodnutelnost problémů
Problém rozhodnout, zda dané w má vlastnost P lze ztotožnit s množinou {w | w má vlastnost P}.
Příklad. Problém rozhodnout, zda daná regulární gramatika reprezentuje konečný jazyk, ztotožníme s jazykem
{G | Q je regulární gramatika a L(Q) je konečný}.
Definice. Problém P odpovídající jazyku /_ = {1/1/1 w má vlastnost P} je
■ rozhodnutelný, právě když L\e rekursivní,
■ nerozhodnutelný, právě když L není rekursivní,
■ částečně rozhodnutelný (semirozhodnutelný), právě když L je rekursivně spočetný.
IB102 Automaty a gramatiky, 16.12.2019
15/16
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)	Tu ringový 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, 16.12.2019
16/16