Vztah derivací a derivačních stromů
V této kapitole se budeme zabývat vztahem mezi derivací a derivačním stromem. Na začátek si
uvedeme větu, kterou si i dokážeme.
Věta.
Buď G = (N, Σ, P, S) bezkontextová gramatika. Pak pro libovolné α ∈ (N ∪ Σ)∗
platí: S ⇒∗
α,
právě když v G existuje derivační strom s výsledkem α.
Důkaz. Buď A ∈ N označme GA = (N, Σ, P, A). Nyní se pokusíme dokázat tvrzení A ⇒∗
α,
právě když v GA existuje derivační strom s výsledkem α. Tvrzení věty poté získáme díky
nahrazením neterminálu A za počáteční neterminál S.
⇐: Předpokládejme, že v GA existuje derivační strom s výsledkem α, A ∈ N, α ∈ (N ∪ Σ)∗
.
Dále předpokládejme, že derivační strom má k vnitřních uzlů (k ∈ N). Důkaz provedeme indukcí
vzhledem ke k.
1. Báze: k = 1
Má-li derivační strom jediný vnitřní uzel, pak se jedná o neterminál A, ze kterého vedou
hrany do listů α1α2 . . . αm. To znamená, že v GA je pravidlo A → α1α2 . . . αn, neboli
A → α. Tím pádem platí A ⇒∗
α a báze je prokázána.
2. Indukční předpoklad: předpokládejme, že pro derivační strom T s k − 1 vnitřními uzly
tvrzení B ⇒∗
α platí, kde B je kořen stromu T .
3. Indukční krok: uvažujme derivační strom R s kořenem A o k vnitřních uzlech s výsledkem
α. Označme následníky kořene A jako x1, x2, . . . , xm.
a) je-li xi list, pak αi = xi
b) je-li xi vnitřní uzel, pak xi je kořenem podstromu Ti, který má maximálně k − 1
vnitřních uzlů (protože A už není vnitřním uzlem Ti). Podle indukčního předpokladu
lze xi ⇒∗
αi. Výsledkem stromu R je řetězec α1α2α3 . . . αm.
Celkově tedy dojde k této postupné derivaci neterminálu A:
A ⇒ x1x2 . . . xm ⇒
⇒ α1x2 . . . xm ⇒∗
⇒∗
α1α2 . . . xm ⇒∗
⇒∗
α1α2α3 . . . αm = α
Platí A ⇒∗
α a indukční krok je dokázán.
⇒: Předpokládejme, že A ⇒∗
α. Provedeme indukci vzhledem k počtu odvození.
1. Báze: k =1
A ⇒ α, tím pádem A → α ∈ P a existuje derivační strom s kořenem A a výsledkem α.
2. Indukční předpoklad: předpokládejme, že existuje derivační strom s kořenem A a výsledkem
α, kde A ⇒k−1
α.
3. Indukční krok: Nechť A ⇒k
α. Předpokládejme, že první derivace je A ⇒ x1x2 . . . xn.
Následně můžou nastat tyto dvě situace:
1
• xi je terminál, tím pádem xi = αi.
• Pokud xi není terminál, lze z něj odvodit v k −1 krocích symbol αi – 1. krok jsme již
provedli odvozením A ⇒ x1x2 . . . xn, zbývá jich tedy už jen k − 1. Podle indukčního
předpokladu existuje derivační strom s kořenem xi a výsledkem αi.
Spojíme-li všechny terminální xi s výsledky podstromů, jejichž kořenem je neterminál xi,
získáme řetězec α1α2 . . . αn = α, tj. v GA existuje derivační strom s výsledkem α.
Poznámka.
Věta, kterou jsme dokázali, má i praktický účel. Pokud za řetězec α dosadíme nějaké slovo w,
pak z tvrzení vyplývá:
S ⇒∗
w ⇐⇒ v gramatice G existuje derivační strom s výsledkem w.
To však neznamená, že musí být pouze jeden. V příkladech z minulé hodiny jsme si ukazovali
gramatiky a slova, pro která vždy byl pouze jeden derivační strom. Obecně to tak není.
Příklad 1.
Buď G = ({E}, {i, +, ∗, (, )}, P, E) bezkontextová gramatika s pravidly:
P = {E → E + E | E ∗ E | (E) | i}
Pro slovo w = i + i + i ∈ L(G) existují 2 derivační stromy:
E
E +
+E E
E
i i
i
2
+
+
E
i
E
E
E E
ii
Víceznačná gramatika
Definice – víceznačná gramatika
Bezkontextová gramatika se nazývá víceznačná, právě když existuje alespoň jedno slovo w ∈
L(G) takové, že pro něj nalezneme minimálně 2 derivační stromy. V opačném případě, tj. když
pro každé slovo w ∈ L(G) existuje právě jeden derivační strom, říkáme, že G je jednoznačná
gramatika.
Definice – víceznačný jazyk
Jazyk L se nazývá vnitřně víceznačný právě tehdy když každá gramatika, která jej generuje, je
víceznačná.
Příklad 2.
Gramatika G z příkladu 1 je víceznačná. Generuje jazyk všech aritmetických výrazů s operátory
+, ∗, (, ). Tento jazyk není vnitřně víceznačný, protože následující gramatika H, která jej
generuje také, je jednoznačná:
H = ({E, T, F}, {i, (, ), +, ∗}, P, S)
P = {E → E + T | T,
T → T ∗ F | F,
F → (E) | i}
3
Příklad 3.
Je dána gramatika G = ({S, A, B}, {a, b}, P, S), kde množina pravidel
P = {S → aB | abA | bS | bAa,
A → aaA | b,
B → bB | b}
Dokažte, že gramatika G je víceznačná, tj. nalezněte slovo w ∈ L(G), pro které existují minimálně
dva různé derivační stromy.
Příklad 4.
Mějme následující dva jazyky nad abecedou {a, b}∗
: L1 = {ab, baa}, L2 = {b, aab}. Pro oba
jazyky nalezněte víceznačné gramatiky, které je generují. Ukažte, proč jsou víceznačné.
Příklad 5.
Dokažte, že jazyky L1, L2 z příkladu 4 nejsou vnitřně víceznačné.
Příklad 6.
Rozhodněte, zda platí či neplatí následující čtyři tvrzení:
• Je-li jazyk L vnitřně víceznačný, pak existuje víceznačná gramatika G, která jej generuje.
• Je-li jazyk L vnitřně víceznačný, pak existuje jednoznačná gramatika G, která jej generuje.
• Je-li gramatika G víceznačná, pak jazyk L(G) je též víceznačný.
• Je-li gramatika G jednoznačná, pak jazyk L(G) je též jednoznačný.
Svá tvrzení zdůvodněte.
4