Intuice k C-Y-K algoritmu
S ->• AB | CD | EF Platí S ^* iv ?
IB102 Automaty a gramatiky, 9.12.2019
1/18
Intuice k C-Y-K algoritmu
Problém: Lze v dané gramatice v CNF vygenerovat dané slovo w?
Ř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
mu — abc
IB102 Automaty a gramatiky, 9.12.2019
2/18
S AB | SS | a
/\ A4 | BC | a
e -)■ /\e i b
C -> S/A I í)
Příklad
Platí S ^* aĎaa
IB102 Automaty a gramatiky, 9.12.2019
Příklad
S ->• AB I SS A     AA | BC B ^ AB \ b C ^ SA \ b
a a
Tíj= {XeN\X w = abaa
1
1
3 2 1
3 2 1
b
b
IB102 Automaty a gramatiky, 9.12.2019
Algoritmus Cocke-Younger-Kasami
Vstup: gramatika Q = (A/, Z, P, S) v CNF, slovo w = ...wn^s Výstup: množiny T,-j = {X g N \ X =>* w,... wi+j_^}
1: for / <r-1 to n do
2:       7},! <- 0
3:     for all pravidlo tvaru (A -» a) g P do 4: if a = w,- then T/?1 <- 7/?1 u {A}
5. for y ^ 2 to n do
6:     for / 4- 1 to n-j + 1 do
8: for k <r-1 to y - 1 do
9: for all pravidlo tvaru (A    SC) g P do
10: if e g TÍ9K A C g 7}+^.^ then Tid <- Tid u {/l}
IB102 Automaty a gramatiky, 9.12.2019
5/18
Vlastnosti bezkontextových jazyků
Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (£2) je uzavřena vzhledem k operacím:
D sjednocení
B zřetězení
B iterace
□ pozitivní iterace
B průnik s regulárním jazykem
Věta 3.60. Třída bezkontextových jazyků (£2) není uzavřena vzhledem k operacím:
□ průnik
B doplněk
IB102 Automaty a gramatiky, 9.12.2019
6/18
Sjednocení
L-i je generován CFG Q\ = (A/-|, Z1, P1, Si) a /_2 je generován CFG £2 = (A/2,512, ^2, S2).
Bez újmy na obecnosti můžeme předpokládat A/-| n A/2 = 0.
Definujeme 5 = (A/1uA/2u {S}, Z1 u Z2, P, S), kde S je nový symbol a
p = p1 u P2 u {S -> Si, S -> S2}.
Každá derivace v £ začne použitím buď S    S-i nebo S    S2. Podmínka A/-| n A/2 = 0 zaručí, že při použití S ^ S-i (resp. S    S2) lze v dalším derivování používat jen pravidla z Pí (resp. P2).
Jazyk /_ = L-i u /_2 je generován gramatikou
IB102 Automaty a gramatiky, 9.12.2019
7/18
Zřetězení
L-i je generován CFG    = (A/-|, Z-i, P-i, S-i) a L2 je generován CFG Q2 = (A/2,5Z2, P2, S2).
Bez újmy na obecnosti můžeme předpokládat A/-| n N2 = 0.
Definujeme 5 = (A/1uA/2u {S}, Z1 u Z2, P, S), kde S je nový symbol a
P = P1uP2u{S^ S1S2}.
Jazyk L = L| .L2 je generován gramatikou
IB102 Automaty a gramatiky, 9.12.2019 8/18
Iterace a pozitivní iterace
L-i je generován CFG    = (A/-|, Z1, P1, ).
Definujeme g = (N^u {S}, Z1, P, S), kde S je nový symbol a
Jazyk L = L* je generován gramatikou
Definujeme g = (N^u {S}, Z1, P, S), kde S je nový symbol a
P=PiU{S^SSi |
Jazyk L = Lj je generován gramatikou g.
IB102 Automaty a gramatiky, 9.12.2019
9/18
Korektnost konstrukce pro iteraci
Dokážeme L(Q) = L*v
IB102 Automaty a gramatiky, 9.12.2019
10/18
Průnik a doplněk
U = {anbncm | m, n > 1} /_2 = {ambncm \ m, n > 1} Oba tyto jazyky jsou CFL.
Kbyby C2 byla uzavřena vzhledem k operaci průniku, pak by i
L| n L2 = {anbnď | n > 1} musel být bez kontextový, což však není.
Neuzavřenost £2 vůči doplňku plyne z její uzavřenosti na sjednocení, neuzavřenosti na průnik a z De Morganových pravidel:
L-| n L2 = co-(co-/_-| u co-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, 9.12.2019
11/18
Protipříklad k uzavřenosti na doplněk
L = {ww | w g {a, by} není CFL. co-L je CFL.
IB102 Automaty a gramatiky, 9.12.2019
12/18
Průnik s regulárním jazykem
L= L(V),kdeV\e PDA V = (Qu Z, l~, či, Qi, Z0, F|)
fí = /_(.4), kde .4 je deterministický FA A = (Q2,51, <52, q2, ^2)
Sestrojíme PDA p' takový, že L(p') = L n R
p' = (Q, E, r, 5, Qo, Zo, F), kde
■ Q = Qi x Q2
■ Qo = (<71, <fc>
■ F = F-\ x f2
■ 5 : pro každé p e q1, q e Q2, a e 51 u {e}, Z e r platí:
č«p,q>,a,Z) = {«p',c/>,7) I (p/,7)e51(p,a,Z)a«52(Q,a) = c7/} Zřejmě platí w e L(V) ^we L(P) n L(.A).
IB102 Automaty a gramatiky, 9.12.2019 13/18
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 e 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, 9.12.2019
14/18
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 e L(Q) takové, že m < \z\ < n.
Důkaz. Předpokládejme, že Q je v CNF
Nechť p, q jsou čísla s vlastnostmi popsanými v Lemmatu o vkládání. Položme m = pa n = p + q.
(<==) Jestliže z g L{Q) je takové slovo, že |z| > p, pak existuje rozdělení z = uvwxy splňující vx ^ e a uv'wx'y e L(Q) pro všechna / > 0. Tedy jazyk L(Q) obsahuje nekonečně mnoho slov tvaru uv'wx'y, je tedy nekonečný.
IB102 Automaty a gramatiky, 9.12.2019
15/18
(=4>) Nechť 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, |iwx| < q a uv'wx'y e L(Q) pro všechna / > 0.
Pro / = 0 dostáváme, že uwy e L(Q) a současně \uwy\ < \uvwxy
Z nerovností \uvwxy\ > p + q a |iwx| < q plyne, že
UWYI > (P + Q) - Q = P- Tec|y uwy e M, což je spor s volbou z jako slova zMs minimální délkou. Celkem tedy musí být \z\ < p + q. □
IB102 Automaty a gramatiky, 9.12.2019
16/18
Vlastnost sebevložení
Definice 3.70. Nechť Q = (A/, Z, P, S) je CFG. Řekneme, že Q má vlastnost sebevložení, jestliže existují A e N a u, v e Z+ taková, že
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. Viz skripta.
IB102 Automaty a gramatiky, 9.12.2019
17/18
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) = Z* či nikoliv.
Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z nerozhodnutelnosti problému univerzality).
IB102 Automaty a gramatiky, 9.12.2019
18/18