Intuice k C-Y-K algoritmu
S ->• AB Platí S
CD EF
w
1
IB102 Automaty a gramatiky, 3.12. 2012
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, 3.12. 2012
2
Příklad
S -» AB | SS A      AA | BC B ^ AB \ b C      SA I b
a a
platí S =>* afraa ?
IB102 Automaty a gramatiky, 3.12.2012
3
Příklad
S A B
C
AB AA AB SA
SS BC b b
a a
Tij= {X e N | X WiWi+1... wí+j-x} w  = abaa
3 2 1
3 2 1
a
a
a
a
a
a
IB102 Automaty a gramatiky, 3.12.2012
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 = wí 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 Tiik A C G Ti+ifethen T,,, := T,,, U {A} fi 22 od od od od
IB102 Automaty a gramatiky, 3.12. 2012
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, 3.12. 2012
6
Sjednocení
L\ je generován CFG Q\ = (iVi, Si, Pi, S\) a L2 je generován CFG Q2 = (iV2, £2, Pí, S2)
Bez újmy na obecnosti můžeme předpokládat Ni n N2 = 0.
Definujeme £ = (iVi U iV2 U {S}, £1 U £2, P, 5), kde 5 je nový symbol a
P = Px U P2 U {S -> Si, S -> £2}
Každá derivace v Q začne použitím bud S S\ nebo 5 S2-Podmínka Ni n N2 = 0 zaručí, že při použití S —> Si (resp. 5 —>> 52) lze v dalším derivování používat jen pravidla z Pi (resp. P2).
Jazyk L = Li U i/2 je generován gramatikou C/.
IB102 Automaty a gramatiky, 3.12. 2012
7
Zřetězení
Li je generován CFG Q\ = (iVi, Si, Pi, Si) a L2 je generován CFG £2 = (A^>, £2, P2, £2)
Bez újmy na obecnosti můžeme předpokládat iVi niV2
Definujeme č/ = (iVi U^U {5}, £1 U E2, P, S), kde 5 je je nový symbol a
P = PiUP2U{5^ 6162}
Jazyk L = L\.Ľ2 je generován gramatikou č?.
IB102 Automaty a gramatiky, 3.12. 2012
Iterace a pozitivní iterace
L\ 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, 3.12. 2012
Korektnost konstrukce pro iteraci
Dokážeme L{Q) = L\.
IB102 Automaty a gramatiky, 3.12. 2012
10
Průnik a doplněk
Li = {anbncm | m, n > 1}      L2 = {am6ncm | m, n > 1} Oba tyto jazyky jsou CFL.
Kbyby C2 byla uzavřena vzhledem k operaci průniku, pak i L\ n L2 {anbncn I n > 1} musel být bez kontextový, 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 Morganových pravidel:
L\ n Z/2 = co-(co-Li U c0-L2),
tj., kdyby £2 byla uzavřena na doplněk, musela by být uzavřena i na průnik, což však není.
IB102 Automaty a gramatiky, 3.12. 2012
11
Průnik s regulárním jazykem
L = L(V), kde V je PDA V = (Qi, S, I\ S1,q1, Z0, Fx)
i? = L(vA), kde *A je deterministický FA A = (Q2, E, 62, q2, ^2)
Sestrojíme PDA     takový, že L(P')=L n i?.
P' = (Q,E,r,<5,g0,£o,ir), kde
• Q = Qi x Q2
• Qo = («71,92)
• F = Fi x F2
• ô : pro každé p g Qi, 9 £ Q2. a g E u {e}, ZgT platí: 6({p,q),a,Z) = {({p', q') n) I (p',7) e ôi(p,a,Z) a S(tf,a) =
Zrejme platí w G L(P') <^ w G        n L(A).
IB102 Automaty a gramatiky, 3.12. 2012
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, 3.12. 2012
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, 3.12. 2012
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
< g a uvlwxly G L(Q)
Pro i = 0 dostáváme, že uwy G L(Q) a současně |íxíi;í/| < \uvwxy
Z nerovností
< g plyne, že  uwy >
uvwxy] > p + q a \vwx (p + q) — q = p. Tedy iaíi;í/ £ 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, 3.12. 2012
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.2012
IB102 Automaty a gramatiky, 3.12. 2012
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(G) = S* či nikoliv.
Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z nerozhodnutelnosti problému univerzality).
IB102 Automaty a gramatiky, 3.12. 2012
17