Bezkontextové jazyky
Bezkontextová gramatika (context-free grammar, CFG) G je
čtveřice (N, , P, S), kde
* N je neprázdná konečná množina neterminálních symbolů,
*  je konečná množina terminálních symbolů taková, že N   = 
(značení: V = N  ),
* S  N je počáteční neterminál,
* P  N × V 
je konečná množina pravidel.
Jazyk je bezkontextový, pokud je generovaný nějakou bezkontextovou
gramatikou.
IB102 Automaty a gramatiky, 27. 10. 2008 1
Příklad
G = ({E, T, F}, {+, , (, ), i}, P, E), kde P obsahuje pravidla
E  E + T | T
T  T  F | F
F  (E) | i
IB102 Automaty a gramatiky, 27. 10. 2008 2
Derivační stromy pro bezkontextové gramatiky
Definice 3.1. Nechť G = (N, , P, S) je CFG.
Strom T nazveme derivačním stromem v G právě když
1. kořen má návěští S, vnitřní uzly mají návěští z N, listy mají navěští
z N    {},
2. má-li vnitřní uzel návěští A a jeho všichni synové n1, . . . , nk
mají v uspořádání zleva doprava návěští X1, . . . , Xk  V , pak
A  X1 . . . Xk  P,
3. každý list s návěštím  je jediným synem svého otce.
Výsledkem derivačního stromu T nazveme slovo vzniklé zřetězením
návěští listů v uspořádání zleva doprava.
IB102 Automaty a gramatiky, 27. 10. 2008 3
Vztah mezi derivačními stromy a relací 
Věta 3.3. Nechť G = (N, , P, S) je CFG. Pak pro libovolné
  (N  )
platí S 
 právě když v G existuje derivační strom s
výsledkem .
Důkaz. Označme GA
def
= (N, , P, A), kde A  N. Dokážeme, že pro
každé A  N platí
A 
  v GA existuje derivační strom s výsledkem 
(=) Nechť  je výsledkem derivačního stromu, který má k vnitřích
uzlů. Indukcí vzhledem ke k ukážeme, že pak A 
.
Základní krok k = 1:
IB102 Automaty a gramatiky, 27. 10. 2008 4
Indukční krok k > 1:
(IP) Tvrzení platí pro stromy s k - 1 vnitřními uzly.
Strom T s k uzly:
* je-li Xi list, označme i = Xi
* není-li Xi list, pak i je výsledkem podstromu Ti s kořenem Xi
* Výsledek T je 1 . . . n.
Platí: Xi 
i (pro Xi, které není listem, podle (IP))
A  X1 . . . Xn  P (z definice deriv. stromu)
Dostáváme A  X1 . . . Xn 
1 . . . n.
IB102 Automaty a gramatiky, 27. 10. 2008 5
(=) Nechť A 
. Ukážeme, že v GA existuje derivační strom
s výsledkem . Použijeme indukci k délce odvození A 
.
Základní krok A
0
 : Pak  = A a odpovídající derivační strom
má jen jeden uzel (kořen je list) s označením A.
Indukční krok A
k+1
 , k  0:
(IP) Pro každé B  N platí: pokud B 
 v nejvýše k krocích,
pak v GB existuje derivační strom s výsledkem .
A
k+1
  = A  X1 . . . Xn
k
 1 . . . n, kde Xi
k
 i
Konstrukce stromu s výsledkem :
2
IB102 Automaty a gramatiky, 27. 10. 2008 6
Jednoznačnost derivačních stromů
Derivace je sekvence S  1  2  . . .  n.
Levá (resp. pravá) derivace je taková derivace, kde každé i+1 vznikne
z i přepsáním nejlevějšího (resp. nejpravějšího) neterminálu.
Každému derivačnímu stromu odpovídá jediná levá derivace.
Každé levé derivaci odpovídá jediný derivační strom.
Analogicky pro pravou derivaci.
Existuje pro každé   L(G) právě jeden derivační strom?
IB102 Automaty a gramatiky, 27. 10. 2008 7
Definice 3.7. CFG G se nazývá víceznačná (nejednoznačná) právě
když existuje w  L(G) mající alespoň dva různé derivační stromy.
V opačném případě říkáme, že G je jednoznačná.
Jazyk L se nazývá vnitřně (inherentně) víceznačný právě když každá
gramatika, která jej generuje, je víceznačná.
IB102 Automaty a gramatiky, 27. 10. 2008 8
Kanonické tvary bezkontextových gramatik
* redukované bezkontextové gramatiky
* gramatiky bez -pravidel
* gramatiky bez jednoduchých pravidel
* gramatiky bez levé rekurze
* Chomského normální forma
* Greibachové normální forma
IB102 Automaty a gramatiky, 27. 10. 2008 9
Redukované bezkontextové gramatiky
Definice 3.7 Symbol X  N   je nepoužitelný v CFG G =
(N, , P, S) právě když v G neexistuje derivace tvaru
S 
wXy 
wxy
pro žádné w, x, y  
. Řekneme, že G je redukovaná, jestliže
neobsahuje žádné nepoužitelné symboly.
Nepoužitelnost typu I: neexistuje w  
splňující A 
w
Nepoužitelnost typu II: neexistují ,   (N)
splňující S 
A
IB102 Automaty a gramatiky, 27. 10. 2008 10
Nalezení nepoužitelných symbolů typu I
(neexistuje w  
: A 
w)
Vstup: CFG G = (N, , P, S)
Výstup: Ne = {A | w  
. A 
w}
1 i := 0; N0 := 
2 repeat i := i + 1
3 Ni := Ni-1  {A | A    P,   (Ni-1  )
}
4 until Ni = Ni-1
5 Ne := Ni
IB102 Automaty a gramatiky, 27. 10. 2008 11
Věta. Nechť G = (N, , P, S) je CFG taková, že L(G) = . Položme
G
= (Ne, , P
, S), kde P
= P  Ne × (Ne  )
. Pak G
je CFG bez
nepoužitelných neterminálů typu I a L(G) = L(G
).
Důkaz. Dokážeme A  Ne  w  
.A 
w.
(=) Indukcí k i dokážeme A  Ni = w  
. A 
w
Základní krok i = 0: Platí triviálně, protože N0 = .
Indukční krok: (IP) Tvrzení platí pro i. Dokážeme pro i + 1.
* A  Ni. Tvrzení plyne z (IP).
* A  Ni+1 Ni. Pak existuje A  X1 . . . Xk  P,
kde každé Xj je terminál nebo neterminál patřící do Ni.
Podle (IP) existuje wj tak, že Xj 
wj.
Tedy A  X1 . . . Xk 
w1X2 . . . Xk 
. . . 
w1 . . . wk,
kde w1 . . . wk  
.
IB102 Automaty a gramatiky, 27. 10. 2008 12
(=) Indukcí k n dokážeme
A
n
 w, w  
= A  Ni pro nějaké i
Základní krok n = 1: A  w  P okamžitě dává i = 1.
Indukční krok: (IP) Předpokládejme, že dokazované tvrzení platí pro
všechna n
 n.
Nechť A
n+1
 w. A  X1 . . . Xk
n
 w, kde Xj
nj
 wj a nj  n.
Pokud Xj  N, pak podle (IP) Xj  Nij
pro nějaké ij.
Pokud Xj  , klademe ij = 0.
Položme i = 1 + max{i1, . . . , ik}. Pak zřejmě A  Ni. 2
IB102 Automaty a gramatiky, 27. 10. 2008 13
Důsledek 3.10. Existuje algoritmus, který pro libovolnou danou CFG
G rozhoduje, zda L(G) = .
Důkaz. Stačí ověřit, zda S  Ne. 2
IB102 Automaty a gramatiky, 27. 10. 2008 14
Nalezení nepoužitelných symbolů typu II
(neexistují ,   (N  )
: S 
A)
Vstup: CFG G = (N, , P, S)
Výstup: CFG G
= (N
, 
, P
, S) bez nedosažitelných symbolů
splňující L(G) = L(G
)
1 i := 0; Vi := {S}
2 repeat i := i + 1
3 Vi := Vi-1  {X  N   | A  Vi-1 . A  
X
 P}
4 until Vi = Vi-1
5 N
:= N  Vi; 
:=   Vi; P
:= P  (Vi × V 
i )
Korektnost: A  N
 
 ,   (N
 
)
. S 
A
IB102 Automaty a gramatiky, 27. 10. 2008 15
Příklad
IB102 Automaty a gramatiky, 27. 10. 2008 16
Eliminace nepoužitelných symbolů
Věta 3.11. Každý neprázdný bezkontextový jazyk L je generován
nějakou redukovanou CFG.
Důkaz. Nechť L je generován nějakou CFG G.
Krok 1. Z G odstraníme symboly typu I (výsledek označme G1).
Krok 2. Z G1 odstraníme symboly typu II (výsledek označme G2).
IB102 Automaty a gramatiky, 27. 10. 2008 17
Korektnost: Sporem dokážeme, že G2 je redukovaná CFG.
Předpokládejme, že G2 má nepoužitelný symbol X.
* v G2 existuje derivace S 
G2
X
* všechny symboly z G2 jsou též v G1
* pro nějaký terminální řetěz w platí S 
G2
X 
G1
w
* žádný symbol z derivace X 
G1
w není krokem 2 eliminován a
proto X 
G2
w
Víme tedy, že existuje derivace S 
G2
X 
G2
w, kde w je terminální
řetěz. To je ve sporu s předpokladem, že X je v G2 nepoužitelný. 2
IB102 Automaty a gramatiky, 27. 10. 2008 18