Deterministické zásobníkové automaty Definice 3.72. Řekneme, že PDA M = (Q,Y,,r,5,q0,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 5(q, a, Z) = 0 pro všechna a £ S; 2. pro žádné g £ Q, Z £ T a a £ E U {e} neobsahuje 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, 10.12.2012 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, 10.12.2012 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 — \Y\ r = max{|7| | (j/,7) G 5(p,s,Z), p,pf GQ, 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, 10.12.2012 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 ô(p, e, Z), p,pr e Q, Z e T} IB102 Automaty a gramatiky, 10.12.2012 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, 10.12.2012 5 Průnik a sjednocení Věta. Třída DCFL není uzavřena na průnik. Důkaz. Li = {an6ncm | rri.n > 1} a L2 = {arnbncrn \ m,n > 1} jsou DCFL, ale L\ n Z^ = {an6ncn | 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: Li 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, 10.12.2012 6 Vztah deterministických a nedeterministických CFL Věta. Třída DCFL tvoří vlastní podtřídu třídy bez kontextový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, 10.12.2012 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, 10.12.2012 8 Turingův stroj - syntaxe Definice. Turingův stroj (TM) je M = (Q, E, T, >, U, 5, q0, qacc, qTei), kde • Q je konečná množina, jejíž prvky nazývame 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, i?} 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, 10.12. 2012 9 Dále požadujeme, aby pro každé q G Q existoval p G Q takový, že S(q, >) = (p, >,i2) (tj. > nelze přepsat ani posunout hlavu za okraj pásky). Označení. UW = UUUUUU... Definice. Konfigurace Turingova stroje je trojice (g, z, n) eQx{y\Ju y e T*} x N0, kde • q je stav, • j/Uw je obsah pásky, • n značí pozici hlavy na pásce. Počáteční konfigurace pro vstup w G S* je trojice (#0, >w\Ju,0). Akceptující konfigurace je každá trojice tvaru (<7acc52,n). Zamítající konfigurace je každá trojice tvaru (qTe^z,ri). IB102 Automaty a gramatiky, 10.12.2012 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 (^o 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 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, 10.12.2012 11 Výpočet TM Ai na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací Kq, K\, K2, ..kde Kq je počáteční konfigurace pro w a Kí \-^-Ki+i pro všechna i > 0. Stroj Ai akceptuje slovo w právě když výpočet Ai na w je konečný a jeho poslední konfigurace je akceptující. Stroj A4 zamítá slovo w právě když výpočet A4 na n; 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 n; je nekonečný. Jazyk akceptovaný TM definujeme jako L (M) = {w eY,* \ M akceptuje w}. IB102 Automaty a gramatiky, 10.12.2012 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, 10.12.2012 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ýva rekursivní, pokud je akceptovaný nějakým úplným Tu ringovým strojem. IB102 Automaty a gramatiky, 10.12.2012 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ý | w má vlastnost P} není rekursivní • částečně rozhodnutelný (semirozhodnutelný) {w \w n\i vlastnost P} je rekursivně spočetná IB102 Automaty a gramatiky 10.12.2012 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) 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, 10.12.2012 16