Rozhodnutelné problémy pro bezkontextové jazyky
Problém příslušnosti
Existuje  algoritmus,   který  pro  libovolnou  danou  CFG  Q  a  slovo w rozhoduje, zda w £ L(Q) či nikoliv.
Problém prázdnosti
Existuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L{Q) = 0 či nikoliv.
Problém konečnosti
Existuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L(Q) je konečný či nikoliv.
IB102 Automaty a gramatiky, 14.12.2009
1
Konečnost
Věta 3.68.   Ke každé CFG Q lze sestrojit čísla m,n taková, že L{Q) je nekonečný právě když existuje slovo z G L{Q) takové, že  m < \z\ < n.
Důkaz. Předpokládejme, že Q je v CNF.
Necht p, g jsou čísla s vlastnostmi popsanými v Lemmatu o vkládání. Položme m=pan=p + g.
(<=) Jestliže z G L{Q) je takové slovo, že \z\ > p, pak existuje rozdělení z = uvwxy splňující ra/n uvlwxly G L{Q) pro všechna i > 0. Tedy jazyk L(Q) obsahuje nekonečně mnoho slov tvaru uvlwxly, je tedy nekonečný.
IB102 Automaty a gramatiky, 14.12.2009
2
55
(=>) Necht L (Q) je nekonečný. Pak obsahuje i nekonečně mnoho slov délky větší než p - tuto množinu slov označme M. Zvolme z M libovolné takové slovo z, které má minimální délku a ukažme, že musí platit p < \z\ < p + q.
Kdyby \z\ > p + g, pak (opět dle Pumping lemmatu pro CFL) lze z
psát ve tvaru z = uvwxy, kde vx ^ e, pro všechna i > 0.
vwx
< q a uvlwxly G L{Q)
Pro i = 0 dostáváme, že uwy G L{Q) a současně \uwy\ < \uvwxy
Z nerovností \uvwxy\ > p + q a |viral < g plyne, že \uwy > {p + q) — Q — P- Tedy uwy G M, což je spor s volbou z jako slova z M s minimální délkou. Celkem tedy musí být \z\ < p + q.             n
IB102 Automaty a gramatiky, 14.12.2009
3
Vlastnost sebevložení
Definice 3.70. Necht Q = (TV, E, P, S) je CFG. Řekneme, že Q má vlastnost sebevložení, jestliže existují ÍGÍVaw,i;G S+ taková, že A =>+ uAv.
CFL L má vlastnost sebevložení, jestliže každá bezkontextová gramatika, která jej generuje, má vlastnost sebevložení.
Věta 3.71. CFL L má vlastnost sebevložení, právě když L není regulární.
Důkaz ve skriptech obsahuje závažnou chybu. Kdo mi jako první pošle mail s popisem chyby, získá 1 tvrdý bod.           Deadline: 31.12.2009
IB102 Automaty a gramatiky, 14.12.2009
4
Nerozhodnutelné problémy pro bezkontextové jazyky
Problém regularity
Neexistuje algoritmus,  který pro libovolnou danou CFG Q rozhoduje,
zda L(Q) je regulární či nikoliv.
(Tedy není rozhodnutelné, zda L(Q) má vlastnost sebevloženíči nikoliv.)
Problém univerzality
Neexistuje algoritmus,  který pro libovolnou danou CFG Q rozhoduje, zda L(G) = S* či nikoliv.
Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z nerozhodnutelnosti problému univerzality).
IB102 Automaty a gramatiky, 14.12.2009
5
Deterministické zásobníkové automaty
Definice  3.72.       Řekneme,  že  PDA M = (Q, E,r,5,g0, Z0,F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky:
1.  pro všechna  q G Q a Z G T  platí:    kdykoliv ö(q,e,Z)  ^ 0,   pak 5(g, a, Z) = 0 pro všechna a G S;
2.  pro žádné gG Q,^Gľa   a G E U {č} neobsahuje 5(g, 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(Á4).
IB102 Automaty a gramatiky, 14.12. 2009                                                                                                                                                                                          6
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, 14.12.2009
7
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.
■v
Řešení: s = \Q\     t — |T|
r = max{|7| | (j/,7) £ 5 (p, £, Z), p,p7 G Q, Z G T}
zásobník neomezeně roste při ^-krocích <<==> během posloupnosti e-kroků jeho délka vzroste o více než r • s • t
IBIO2 Automaty a gramatiky, 14.12.2009
8
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.
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).
IB102 Automaty a gramatiky, 14.12.2009
9
Průnik a sjednocení
Věta. Třída DCFL není uzavřena na průnik.
Důkaz. Li = {cr^c™ \ m,n > 1} a L2 = {am6ncm | m,n> 1} jsou DCFL, ale Li n L2 = {anbncn \ 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 M organových pravidel:
Li n L2 = co-(co-Li U C0-L2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.)            □
IBIO2 Automaty a gramatiky, 14.12.2009
10
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, 14.12.2009
11
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(l) - Yacc, Bison, javacup LL(k) - JavaCC, ANTLR
IB102 Automaty a gramatiky, 14.12.2009
12
Turingův stroj - syntaxe
Definice. Turingův stroj (TM) je M = (Q, E, I\ >, 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 r,
•  \> 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,
•  ?o £ Q je počáteční stav,
•  íacc £ Q je akceptující stav,
•  Qrej £ Q je zamítající stav.
IB102 Automaty a gramatiky, 14.12.2009
13
Dále požadujeme, aby pro každé q £ Q existoval p G Q takový, že 5(g, t>) = (p, t>,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) GQxj^/U^
j/GP}x No, 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, \>wUu,0). Akceptující konfigurace je každá trojice tvaru (qacc,z,n). Zamítající konfigurace je každá trojice tvaru (qre^z,n).
IB102 Automaty a gramatiky, 14.12.2009
14
Výpočet Turingova stroje
Označení. Pro libovolný nekonečný řetěz z nad r, 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 A4 definujeme binární
relaci
M
(krok výpočtu) takto:
{p, z, n)
M
<
V
(q,s%(z),n + l)       pro ô(j>, zn) = (q, b, R) {q,s%(z),n-l)       pro ô(p, zn) = (q, b, L)
IB102 Automaty a gramatiky, 14.12.2009
15
Výpočet TM A4 na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací ifo,ifi,if2v» kde K0 je počáteční konfigurace pro w b Kí \-j^-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 A4 definujeme jako
L (M) = {w G S* | 7W akceptuje w}.
IB102 Automaty a gramatiky, 14.12.2009
16
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, 14.12.2009
17
r                           ___
Úplný Turingův stroj a rekursivní jazyky
Definice. Turingův stroj se vstupní abecedou S se nazýva úplný, pokud každé wjgE* 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, 14.12.2009
18
Rozhodnutelné a nerozhodnutelne 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 | w má vlastnost P} není rekursivní
•  částečně rozhodnutelný (semirozhodnutelný)  <^^>
<^^>   {w | w má vlastnost P} je rekursivně spočetná
IB102 Automaty a gramatiky, 14.12.2009
19
Přehled jazykových tříd
Jazyky	Gramatiky (typ)	Automaty
rekursivně spočetné	frázové (0)	Tu ringový stroje
rekursivní	-	úplné Turingovy stroje
kontextové	kontextové (1)	lineárně ohraničené TM
bezkontextové	bez kontextové (2)	zásobníkové automaty
deterministické CFL	-	deterministické PDA
regulární	regulární (3)	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, 14.12.2009
20