Intuice k C-Y-K algoritmu
S AB Platí S
CD EF
w
1
IB102 Automaty a gramatiky, 5.12. 2011
1
Intuice k C-Y-K algoritmu
Problém: Lze v dané gramatice v CNF vygenerovat dané slovo wl
Řešení: Pro každé neprázdné podslovo u slova w spočítáme množinu Tu všech neterminálů, z kterých lze odvodit u.
• u — a
• u — ob
• u = abc
IB102 Automaty a gramatiky, 5.12. 2011
2
Příklad
S A B
C
AB AA AB SA
ss
BC
b
b
a a
platí S =3-* abaa ?
IB102 Automaty a gramatiky, 5.12.2011
3
Příklad
S A B
C
AB AA AB SA
ss
BC
b
b
a a
Ti:j= {X e N | X WiWi+i... Wi+j-i} w = abaa
4
3 2
4
3 2
a
a
a
a
a
a
IB102 Automaty a gramatiky, 5.12.2011
4
Algoritmus Cocke - Younger - Kasami
Vstup: gramatika q = (iV, S, P, S) v CNF, slovo w = wi.. .wn Poznámky: Tíj = {X <E N \ X =^>*     ... Wí+j-i}, pro w — e zřejmé
1 for i := 1 to n do
2 TM := 0
3 for každé pravidlo A —t a G P do
4 if a = Wi then TM := TM U {A} fi
5 od od
6 for j := 2 to n do
7 for i := 1 to n — j + 1 do s Ti j := 0
g for k := 1 to j — 1 do
for každé pravidlo A —> BC G P do
if P G TÍ9k A C G Tť+ifethen T,,, := T,,, U {A} fi 22 od od od od
IB102 Automaty a gramatiky, 5.12. 2011
5
Vlastnosti bezkontextových jazyků
Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (£2) je uzavřena vzhledem k operacím
1. sjednocení
2. zřetězení
3. iterace
4. pozitivní iterace
5. průnik s regulárním jazykem
Věta 3.60. Třída bezkontextových jazyků (£2) není uzavřena vzhledem k operacím
1. průnik
2. doplněk
IB102 Automaty a gramatiky, 5.12. 2011
6
Sjednocení
Li je generován CFG Q\ = (iVi, Si, Pi, Si) a L2 je generován CFG Q2 = (iV2, £2, P2, S2)
Bez újmy na obecnosti můžeme předpokládat N\ n iV2 = 0.
Definujeme £ = (Nľ U iV2 U {S'}, Ex U E2, P, 5), kde £ je nový symbol a
p = px u P2 U {5    5^1, S -> S2}
Každá derivace v Q začne použitím bud S —t S\ nebo S S2. Podmínka N\ n N2 = 0 zaručí, že při použití S —> Si (resp. S —> S2) lze v dalším derivování používat jen pravidla z P\ (resp. P2).
Jazyk L = L\ U L2 je generován gramatikou č/.
IB102 Automaty a gramatiky, 5.12. 2011
7
Zřetězení
Li je generován CFG Q\ = (iVi, Si, Pi, S\) a L2 je generován CFG Q2 = (^2, S2, P2, S2)
Bez újmy na obecnosti můžeme předpokládat N\ n N2
Definujeme g = (NľUN2U {S}, £1 U E2, ^ 5), kde S je je nový symbol a
P = PiUP2U{5^ 6162} Jazyk L = L\.L2 je generován gramatikou Q.
IB102 Automaty a gramatiky, 5.12. 2011
Iterace a pozitivní iterace
Li je generován CFG Q\ = (iVi, Si, Pi, Si)
Definujeme Q = (iVi U {5}, Ei, P, 5), kde 5 je je nový symbol a
P = PľU{S ^ SSľ I e} Jazyk L = L* je generován gramatikou Q.
Definujeme Q = (iVi U       Ei, P, 5), kde 5 je je nový symbol a
p = P1 u {S ^SSľ I #1}
Jazyk L =     je generován gramatikou Q
IB102 Automaty a gramatiky, 5.12. 2011
Korektnost konstrukce pro iteraci
Dokážeme L{Q) = L\.
IB102 Automaty a gramatiky, 5.12. 2011
10
Průnik a doplněk
Li = {anbncm | m,rc > 1}      L2 = {am6ncm | m,rc > 1} Oba tyto jazyky jsou CFL.
Kbyby C2 byla uzavřena vzhledem k operaci průniku, pak i L\ n L2 {anbncn | n > 1} musel být bezkontextový, což však není.
Neuzavřenost C2 vůči doplňku plyne z její uzavřenosti na sjednocení, neuzavřenosti na průnik a z De Morgánových pravidel:
Li n L2 = co-(co-Li U co-L2),
tj., kdyby C2 byla uzavřena na doplněk, musela by být uzavřena i na průnik, což však není.
IB102 Automaty a gramatiky, 5.12. 2011
11
Průnik s regulárním jazykem
L = L(V), kde V je PDA V = (Qi, E, I\ 5l5 9l, Z0, Fi)
R = Z/(Ä), kde *A je deterministický FA A = (Q25 E, £2,52, F2)
Sestrojíme PDA V' takový, že L(V')=L n i?. P' = (Q, E, r, <5, g0, Zq, F), kde
• Q = Qi x g2
• qo = (91,92)
• F = Fi x F2
• ô : pro každé p G Qi, 9 G Q2. a G E U {s}, Z G T platí: 5({p,q),a,Z) = {((p',q')il) I (p'il) G Si(p,a,Z) a Ô2(q,a) = q'}
Zřejmě platí w G L(P') w e L(F) n L(.A).
IB102 Automaty a gramatiky, 5.12. 2011
12
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, 5.12. 2011
13
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 £ L (Q) takové, že m < \z\ < n.
Důkaz. Předpokládejme, že Q je v CNF.
Necht p, q jsou čísla s vlastnostmi popsanými v Lemmatu o vkládání. Položme m = pan = p + q.
{<=) Jestliže z G L(Q) je takové slovo, že \z\ > p, pak existuje rozdělení z = uvwxy splňující ra/ea 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, 5.12. 2011
14
(=>) 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 + q, 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
<ga 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 \vwx\ < q 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. □
IB102 Automaty a gramatiky, 5.12. 2011
15
Vlastnost sebevložení
Definice 3.70. Necht Q = (iV,S,P,5) je CFG. Řekneme, že Q má vlastnost sebevložení, jestliže existují A £ N a u, v £ S+ taková, že
A ^+ iM?;.
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.2011
IB102 Automaty a gramatiky, 5.12. 2011
16
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(Q) = S* či nikoliv.
Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z nerozhodnutelnosti problému univerzality).
IB102 Automaty a gramatiky, 5.12. 2011
17