Intuice k C-Y-K algoritmu
S — AB | CD | EF Platí S ^* w ?
IB102 Automaty a gramatiky, 6.12.2010
1
Intuice k C-Y-K algoritmu
Problém: Lze v dané gramatice v CNF vygenerovat dané slovo w?
Řešení: Pro kaZde podslovo u slova w spoCítame mnoZinu Tu vsech neterminaiU, z kterých lze odvodit u.
• u = a
• u = ab
• u = abc
IB102 Automaty a gramatiky, 6.12.2010
2
S — AB I SS I a A — AA I BC I a B — AB I b C — SA I b
Příklad
platí S =^>* abaa ľ
IB102 Automaty a gramatiky, 6.12.2010
3
Příklad
S — AB | SS | a Tiyj = {X e N | X ^* Wiwi+1... wi+j-1}
A — AA | BC | a w = abaa
B — AB | b
C — SA | b
1
4		2		
3			3	
2				4
1				
abaa
1
4		2		
3			3	
2				4
1				
abaa
IB102 Automaty a gramatiky, 6.12.2010
4
Algoritmus Cocke - Younger - Kasami
Vstup: gramatika G = (N, S, P, S) v CNF, slovo w = w1... wn Poznámka: T^j = {X | X ^* Wi... wi+j_i}
1 for i := 1 to n do
2 Tť,i := 0
3 for každé pravidlo A — a G P do
4 if a = w, then Ti>1 := TM U {A} i
5 od od
6 for j := 2 to n do
7 for i := 1 to n — j + 1 do
8 Ti,j := 0
9 for k := 1 to j — 1 do
10 for každé pravidlo A — BC G P do
11 if B G Ti9k A C G Ti+k,j-k then T*,, := ThJ U {A} i
12 od od od od
IB102 Automaty a gramatiky, 6.12.2010
5
Vlastnosti bezkontextových jazyků
Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (£2) jě uzavřena vzhledem k operacím
1. sjednocení
2. zřetezen í
3. iterace
4. pozitivn í iterace
5. průnik s reguiarn ím jazykem
Věta 3.60. Trída bezkontextových jazyků (£2) nění uzavřena vzhledem k operac ím
1. průnik
2. doplnřek
IB102 Automaty a gramatiky, 6.12.2010
6
Sjednocení
Li je generován CFG £1 = (Ni, Ei, P\, S\) a L2 je generován CFG £2 = (N2, £2, P2, S2)
Bez újmy na obecnosti můžeme předpokládat N1 n N2 = 0.
Definujeme £ = (N U N U {S}, Ei U E2, P, S), kde S je novy symbol a
P = Pi u P2 U {S — Si, S — S2}
Každa derivace v £ zaCne použitím bud S — Si nebo S — S2. Podmínka Ni n N2 = 0 zaruCí, že pri použití S — Si (resp. S — S2) lze v dalsím derivovaní používat jen pravidla ž Pi (resp. P2).
Jažyk L = Li U L2 je generovan gramatikou £.
IB102 Automaty a gramatiky, 6.12.2010
7
Zřetězení
Li je generován CFG £1 = (Ni, Ei, Pi, Si) a L2 je generován CFG £2 = (N2, £2, P2, S2)
Bez újmy na obecnosti můžeme předpokládat Ni n N2 = 0.
Definujeme £ = (Ni U N2 U {S}, Ei U E2, P, S), kde S je je novy symbol a
P = Pi U P2 U {S SiS2}
Jazyk L = Li.L2 je generovan gramatikou £.
IB102 Automaty a gramatiky, 6.12.2010
8
Iterace a pozitivní iterace
Li je generován CFG gi = (Ni, ei, Pl, Si)
Definujeme g = (N1 u {S}, e1, P, S), kde S je je nový symbol á
P = Pi U {S    SSi | č} Jazyk L =     je generován gramatikou g.
Definujeme g = (Ni u {S}, ei, P, S), kde S je je nový symbol á
P = Pi u {S    SSi | Si}
Jazyk L = L+ je generován gramatikou g.
IB102 Automaty á gramatiky, 6.12.2010
9
Korektnost konstrukce pro iteraci
Dokážeme L(G) = L\.
IB102 Automaty á grámátiky, 6.12.2010
10
Průnik a doplněk
Li = {anbncm | m,n > 1}      L2 = {ambncm | m,n > 1} Oba tyto jazyky jsou CFL.
Kbyby L2 byla uzavřena vzhledem k operaci prUniku, pak i Li n L2 = {anbncn | n > 1} musel byt bezkontextovy, coZ vsak není.
Neuzavrenost L2 vuci doplřku plyne z její uzavřenosti na sjednocení, neuzavřenosti na pmnik a z De Morganovych pravidel:
Li n L2 = co-(co-Li U co-L2),
tj., kdyby L2 byla uzavřena na doplnek, musela by byt uzavrena i na pmnik, coz vsak není.
IB102 Automaty a gramatiky, 6.12.2010
11
Průnik s regulárním jazykem
L = L(P), kde P je PDA P = (Qi, S, r, 5x, qi, Zo, Fi)
R = L (A), kde A je deterministicky FA A = (Q2, S, 52, q2, F2)
Sestrojíme PDA P' takovy, že L(P')=L n R. P' = (Q,S,r,5,qo,Zo,F), kde
• Q = Qi x Q2,
• F = F1 x F2
• 5 : pro každe p G Q1, q G Q2, a G S U {e}, Z G r platí:
5((p,q),a,Z)= {((p',q)   I   (p',Y) G 51(p,a,Z) a <$2(q,a) = q'}
Zrejme platí w G L(P') w G L(P) n L(R).
IB102 Automaty a gramatiky, 6.12.2010
12
Rozhodnutelné problémy pro bezkontextové jazyky
Problém príslušnosti
Existuje algoritmus, který pro libovolnou danou CFG G a slovo w rozhoduje, zda w G L(G) ci nikoliv.
Problém prázdnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje, zda L(G) = 0 ci nikoliv.
Problém konécnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje, zda L(G) je konečný ci nikoliv.
IB102 Automaty a gramatiky, 6.12.2010
13
KoneCnost
Veta 3.68. Ke kážde CFG G lže sestrojit číslá m, n táková, že L(G) je nekonečny práve když existuje slovo z G L(G) tákove, že m < |z| < n.
DUkaz. Předpokládejme, že G je v CNF.
Necht p, q jsou číslá s vlástnostmi popsánymi v Lemmátu o vkládání. Položme m = p á n = p + q.
(^=) Jestliže z G L(G) je tákove slovo, že |z| > p, pák existuje roždelení z = uvwxy splnující vx = e á uvlwxly G L(G) pro vsechná i > 0. Tedy jážyk L(G) obsáhuje nekonečne mnoho slov tváru uvlwxly, je tedy nekonečny.
IB102 Automáty á grámátiky, 6. 12. 2010
14
(=>) Necht L(G) je nekonečny. Pák obsahuje i nekonečne mnoho slov deiky vetsí neZ p - tuto mnoZinu slov označme M. Zvolme z M libovolne tákove slovo z, ktere má minimální delku á ukazme, ze musí plátit p < |z| < p + q.
Kdyby |z| > p + q, pák (opet dle Pumping lemmatu pro CFL) lze z psát ve tvaru z = uvwxy, kde vx = £, |vwx| < q á uv^wx^y G L(G) pro vsechna i > 0.
Pro i = 0 dostáváme, ze uwy G L(G) a současne |uwy| < |uvwxy .
Z nerovností |uvwxy| > p + q á |vwx| < q plyne, ze |uwy > (p + q) — q = p. Tedy uwy G M, coz je spor s volbou z jáko slová z M s minimální delkou. Celkem tedy musí byt |z| < p + q. □
IB102 Automáty á grámátiky, 6. 12. 2010
15
Vlastnost sebevložen í
Definice 3.70. Necht £ = (N, E, P, S) je CFG. Řekneme, že £ ma vlastnost sebevložen í, jestliže existují A G N a u, v G E+ takova, že
A =>+ uAv.
CFL L ma vlastnost sebevložen í, jestliže každa bezkontextova gramatika, ktera jej generuje, ma vlastnost sebevložen í.
Veta 3.71. CFL L ma vlastnost sebevložen í, prave když L nen í regularn í.
Diikaž ve skriptech obsahuje zavažnou chybu. Kdo mi jako prvn í posle mail s popisem chyby, z íska 1 tvrdy bod.        Deadline: 31.12.2010
IB102 Automaty a gramatiky, 6. 12. 2010
16
Nerozhodnutelné problémy pro bezkontextové jazyky
Problém regularity
Neexistuje algoritmus, který pro libovolnou danou CFG G rozhoduje, zda L(G) je regulární ci nikoliv.
(Tedý není rozhodnutelne, zda L(G) ma vlastnost sebevloZení ci nikoliv.) Problem univerzality
Neexistuje algoritmus, který pro libovolnou danou CFG G rozhoduje, zda L(G) = S* ci nikoliv.
Problemy ekvivalence a inkluze take nejsou rozhodnutelne (plýne z nerozhodnutelnosti problemu univerzalitý).
IB102 Automaty a gramatiky, 6.12.2010
17