Intuice k C-Y-K algoritmu
S  AB | CD | EF
Platí S 
w ?
IB102 Automaty a gramatiky, 8. 12. 2008 1
Intuice k C-Y-K algoritmu
Problém: Lze v dané gramatice v CNF vygenerovat dané slovo w?
Řešení: Pro každé podslovo u slova w spočítáme množinu
Tu všech neterminálů, z kterých lze odvodit u.
* u = a
* u = ab
* u = abc
IB102 Automaty a gramatiky, 8. 12. 2008 2
Příklad
S  AB | SS | a
A  AA | BC | a platí S 
abaa ?
B  AB | b
C  SA | b
IB102 Automaty a gramatiky, 8. 12. 2008 3
Příklad
S  AB | SS | a Ti,j= {X  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
a b a a
1
4 2
3 3
2 4
1
a b a a
IB102 Automaty a gramatiky, 8. 12. 2008 4
Algoritmus Cocke - Younger - Kasami
Vstup: gramatika G = (N, , P, S) v CNF, slovo w = w1 . . . wn
Poznámka: Ti,j = {X | X 
wi . . . wi+j-1}
1 for i := 1 to n do
2 Ti,1 := 
3 for každé pravidlo A  a  P do
4 if a = wi then Ti,1 := Ti,1  {A} fi
5 od od
6 for j := 2 to n do
7 for i := 1 to n - j + 1 do
8 Ti,j := 
9 for k := 1 to j - 1 do
10 for každé pravidlo A  BC  P do
11 if B  Ti,k  C  Ti+k,j-k then Ti,j := Ti,j  {A} fi
12 od od od od
IB102 Automaty a gramatiky, 8. 12. 2008 5
Vlastnosti bezkontextových jazyků
Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (L2) 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ů (L2) není uzavřena
vzhledem k operacím
1. průnik
2. doplněk
IB102 Automaty a gramatiky, 8. 12. 2008 6
Sjednocení
L1 je generován CFG G1 = (N1, 1, P1, S1) a
L2 je generován CFG G2 = (N2, 2, P2, S2)
Bez újmy na obecnosti můžeme předpokládat N1  N2 = .
Definujeme G = (N1  N2  {S}, 1  2, P, S),
kde S je nový symbol a
P = P1  P2  {S  S1, S  S2}
Každá derivace v G začne použitím buď S  S1 nebo S  S2.
Podmínka N1  N2 =  zaručí, že při použití S  S1 (resp. S  S2)
lze v dalším derivování používat jen pravidla z P1 (resp. P2).
Jazyk L = L1  L2 je generován gramatikou G.
IB102 Automaty a gramatiky, 8. 12. 2008 7
Zřetězení
L1 je generován CFG G1 = (N1, 1, P1, S1) a
L2 je generován CFG G2 = (N2, 2, P2, S2)
Bez újmy na obecnosti můžeme předpokládat N1  N2 = .
Definujeme G = (N1  N2  {S}, 1  2, P, S),
kde S je je nový symbol a
P = P1  P2  {S  S1S2}
Jazyk L = L1.L2 je generován gramatikou G.
IB102 Automaty a gramatiky, 8. 12. 2008 8
Iterace a pozitivní iterace
L1 je generován CFG G1 = (N1, 1, P1, S1)
Definujeme G = (N1  {S}, 1, P, S), kde S je je nový symbol a
P = P1  {S  SS1 | }
Jazyk L = L
1 je generován gramatikou G.
Definujeme G = (N1  {S}, 1, P, S), kde S je je nový symbol a
P = P1  {S  SS1 | S1}
Jazyk L = L+
1 je generován gramatikou G.
IB102 Automaty a gramatiky, 8. 12. 2008 9
Korektnost konstrukce pro iteraci
Dokážeme L(G) = L
1.
IB102 Automaty a gramatiky, 8. 12. 2008 10
Průnik a doplněk
L1 = {an
bn
cm
| m, n  1} L2 = {am
bn
cm
| m, n  1}
Oba tyto jazyky jsou CFL.
Kbyby L2 byla uzavřena vzhledem k operaci průniku, pak i L1  L2 =
{an
bn
cn
| n  1} musel být bezkontextový, což však není.
Neuzavřenost L2 vůči doplňku plyne z její uzavřenosti na sjednocení,
neuzavřenosti na průnik a z De Morganových pravidel:
L1  L2 = co­(co­L1  co­L2),
tj., kdyby L2 byla uzavřena na doplněk, musela by být uzavřena i na
průnik, což však není.
IB102 Automaty a gramatiky, 8. 12. 2008 11
Průnik s regulárním jazykem
L = L(P), kde P je PDA P = (Q1, , , 1, q1, Z0, F1)
R = L(A), kde A je deterministický FA A = (Q2, , 2, q2, F2)
Sestrojíme PDA P
takový, že L(P
)=L  R.
P
= (Q, , , , q0, Z0, F), kde
* Q = Q1 × Q2,
* q0 = q1, q2
* F = F1 × F2
*  : pro každé p  Q1, q  Q2, a    {}, Z   platí:
( p, q , a, Z) = {( p
, q
, ) | (p
, )  1(p, a, Z) a 2(q, a) = q
}
Zřejmě platí w  L(P
)  w  L(P)  L(R).
IB102 Automaty a gramatiky, 8. 12. 2008 12
Rozhodnutelné problémy pro bezkontextové jazyky
Problém příslušnosti
Existuje algoritmus, který pro libovolnou danou CFG G a slovo w
rozhoduje, zda w  L(G) či nikoliv.
Problém prázdnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje, zda
L(G) =  či nikoliv.
Problém konečnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje, zda
L(G) je konečný či nikoliv.
IB102 Automaty a gramatiky, 8. 12. 2008 13
Konečnost
Věta 3.68. Ke každé CFG G lze sestrojit čísla m, n taková, že L(G) je
nekonečný právě když existuje slovo z  L(G) takové, že m < |z|  n.
Důkaz. Předpokládejme, že G je v CNF.
Nechť p, q jsou čísla s vlastnostmi popsanými v Lemmatu o vkládání.
Položme m = p a n = p + q.
(=) Jestliže z  L(G) je takové slovo, že |z| > p, pak existuje
rozdělení z = uvwxy splňující vx =  a uvi
wxi
y  L(G) pro všechna
i  0. Tedy jazyk L(G) obsahuje nekonečně mnoho slov tvaru
uvi
wxi
y, je tedy nekonečný.
IB102 Automaty a gramatiky, 8. 12. 2008 14
(=) Nechť L(G) 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 = , |vwx|  q a uvi
wxi
y  L(G)
pro všechna i  0.
Pro i = 0 dostáváme, že uwy  L(G) a současně |uwy| < |uvwxy|.
Z nerovností |uvwxy| > p + q a |vwx|  q plyne, že |uwy| >
(p + q) - q = p. Tedy uwy  M, což je spor s volbou z jako slova
z M s minimální délkou. Celkem tedy musí být |z|  p + q. 2
IB102 Automaty a gramatiky, 8. 12. 2008 15
Vlastnost sebevložení
Definice 3.70. Nechť G = (N, , P, S) je CFG. Řekneme, že G má
vlastnost sebevložení, jestliže existují A  N a u, v  +
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. 2008
IB102 Automaty a gramatiky, 8. 12. 2008 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í či nikoliv.
(Tedy není rozhodnutelné, zda L(G) má vlastnost sebevložení či nikoliv.)
Problém univerzality
Neexistuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) = 
či nikoliv.
Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z
nerozhodnutelnosti problému univerzality).
IB102 Automaty a gramatiky, 8. 12. 2008 17