Gramatiky
Definice – gramatika
Gramatikou G rozumíme čtveřici (N, Σ, P, S), kde:
1. N = ∅ je konečná množina tzv. neterminálů.
2. Σ je konečná množina terminálů (terminálních symbolů).
[Označme V = N ∪ Σ.]
3. P je podmnožinou V NV × V je konečná množina pravidel.
4. S ∈ N je počáteční neboli startovní neterminál.
Poznámka.
1. Neterminály označujeme velkými písmeny (A, B, C, . . . ), terminály naopak
označujeme malými písmeny (a, b, c, . . . ).
2. Pro zachování přehlednosti je důležité, aby N ∩ Σ = ∅, tj. abychom v gramatice
nezaváděli symbol, který bude jak neterminálem, tak terminálem.
3. V definici množiny pravidel P se vyskytuje symbol V , který znamená
sjednocení všech terminálních i neterminálních řetězů (V = N ∪Σ). Pokud
zapisujeme V , znamená to libovolný, tedy i nulový počet terminálů či
neterminálů v jakémkoliv pořadí.
4. Prvkem množiny P je dvojice (α, β), kde α obsahuje alespoň jeden neterminál
(plyne z faktu, že α ∈ V NV ). Místo zápisu (α, β) ∈ P používáme
přehlednější α → β a čteme „α přepiš na β .
5. α . . . levá strana pravidla, β . . . pravá strana pravidla.
Příklad 1.
Mějme gramatiku G = ({S, A, B}, {a, b, ε}, P, S), kde množina P = {
S → aA | bbB
aA → aAba
A → aa | bBb | aAa
bB → bbBa
B → b | ε | BB }
Všimněte si, že se v zápisu vyskytuje symbol |. Ten slouží k oddělení dvou
pravidel, které mají stejnou levou stranu. Například: pokud pravidla S → aA,
S → bbB mají na levé straně stejný neterminál S, zapisujeme to zjednodušeně
S → aA | bbB.
1
Definice – přímé odvození v gramatice
Buď G = (N, Σ, P, S) gramatika. Definujeme binární relaci ⇒G na množině V +
,
tj. ⇒G ⊆ V +
× V +
. Pro libovolné dva „řetězce terminálních i neterminálních
symbolů γ, δ platí, že γ ⇒G δ, právě když
1. existuje pravidlo α → β ∈ P a
2. „řetězce terminálních i neterminálních symbolů ϕ, ψ ∈ V
tak, že γ = ϕαψ, δ = ϕβψ. Relaci ⇒G nazýváme přímé odvození.
Příklad 2.
Mějme stejnou gramatiku jako v Příkladu 1, tedy G = ({S, A, B}, {a, b, ε}, P, S),
kde množina P = {
S → aA | bbB
aA → aAba
A → aa | bBb | aAa
bB → bbBa
B → b | ε | BB }
Řetězec aAbaB můžeme odvodit na řetězec abBbbaB, tj.
aAbaB ⇒G abBbbaB
a{A}baB ⇒G a{bBb}baB
Mohli jsme tak učinit, protože v řetězci aAbaB jsme neterminál A nahradili
řetězcem bBb a vznikl výsledek odvození abBbbaB. Tedy použili jsme pravidlo
A → bBb, „vyměnili neterminál A za řetězec bBb a ostatní symboly v řetězci
aAbaB ponechali beze změny a v původním pořadí!
Poznámka.
Všimněte si, že stejně jako u pravidel zapisujeme i odvození „infixově , tj.
symbol přímého odvození ⇒G vkládáme mezi oba řetězce a nepíšeme např.
(aAbaB, abBbbaB) ∈ ⇒G. Určitě jste zaregistrovali proč.
Definice – odvození v k krocích
Buď k ∈ N0. Odvození v k krocích značíme ⇒k
G a definujeme induktivně takto:
1. ⇒0
G je odvození v 0 krocích (např. bB ⇒0
G bB) – tj. neprovede se žádné
odvození.
2. ⇒1
G = ⇒G je přímé odvození (tj. odvození v jednom kroku).
3. ⇒k+1
G = ⇒k
G ◦ ⇒G.
2
Příklad 3.
Znovu použijeme stejnou gramatiku jako v Příkladu 1, tedy G = ({S, A, B}, {a, b, ε}, P, S),
kde množina P = {
S → aA | bbB
aA → aAba
A → aa | bBb | aAa
bB → bbBa
B → b | ε | BB }
Ukázali jsme (v Příkladu 2) odvození aAbaB ⇒G abBbbaB. Můžeme ale pokračovat
dále, tj.
aAbaB ⇒G abBbbaB ⇒G abbbbaB ⇒G abbbba
Všechna tři odvození se však dají souhrně zapsat
aAbaB ⇒3
G abbbba
Provedli jsme tři odvození, tedy odvození ve 3 krocích.
Úkol: Podle jakých pravidel jsme provedli odvození ve 2. a 3. kroku?
Poznámka.
1. Pokud bude z kontextu zřejmě, o jakou gramatiku se jedná, nebudeme v
symbolu odvození používat symbol G, tj. místo ⇒G budeme psát pouze
⇒.
2. V praxi či jiných materiálech se můžete setkat s tím, že se místo pojmu
odvození v gramatice používá derivace v gramatice. Jedná se o dvojí
pojmenování stejné věci.
Příklad 4.
Naši oblíbenou gramatiku snad už ani nemusíme představovat, přesto buď G =
({S, A, B}, {a, b, ε}, P, S), kde množina P = {
S → aA | bbB
aA → aAba
A → aa | bBb | aAa
bB → bbBa
B → b | ε | BB }
Úkol: Zapište odvození slov bb, aaa, bbb, bbba, aaaba, abbba z počátečního neterminálu
S. U každého slova uveďte, jaká pravidla jste použili.
3
Řešení.
1. S ⇒ bbB ⇒ bb, v 1. kroku jsme použili pravidlo S → bbB, ve 2. kroku
pravidlo B → ε.
2. S ⇒ aA ⇒ aaa, v 1. kroku jsme použili pravidlo S → aA, ve 2. kroku
pravidlo A → aa.
3. S ⇒ bbB ⇒ bbb, v 1. kroku jsme použili pravidlo S → bbB, ve 2. kroku
pravidlo B → b.
4. S ⇒ bbB ⇒ bbbBa ⇒ bbba, v 1. kroku jsme použili pravidlo S → bbB, ve
2. kroku pravidlo bB → bbbBa a ve 3. kroku pravidlo B → ε.
5. S ⇒ aA ⇒ aAba ⇒ aaaba, v 1. kroku jsme použili pravidlo S → aA, ve
2. kroku pravidlo aA → aAba a ve 3. kroku pravidlo A → aa.
6. S ⇒ aA ⇒ aAba ⇒ abBbba ⇒ abbba, v 1. kroku jsme použili pravidlo
S → aA, ve 2. kroku pravidlo aA → aAba, ve 3. kroku pravidlo A → bBb
a ve 4. kroku pravidlo B → ε.
Definice – další druhy odvození
Buď k ∈ N0 a nechť G je libovolná gramatika.
• Odvození v nejvýše k krocích:
⇒≤k
=
k
i=0
⇒i
• reflexivní a tranzitivní uzávěr ⇒:
⇒ =
∞
i=0
⇒i
G
• tranzitivní uzávěr ⇒
⇒+
=
∞
i=1
⇒i
Definice – větná forma, věta
Buď G = (N, Σ, P, S) gramatika. Větnou formou rozumíme řetězec α ∈ V ∗
takový, že S ⇒ α. Jsou-li všechny symboly řetězce α terminály, pak α nazýváme
větou.
Příklad 5.
V Příkladu 4 jsme nalezli odvození slov bb, aaa, bbb, bbba, aaaba, abbba v gramatice
G. Jsou to tedy věty. Při odvození slova abbba jsme postupovali takto:
S ⇒ aA ⇒ aAba ⇒ abBbba ⇒ abbba. Řetězce aA, aAba, abBbba jsou tedy větné
formy gramatiky G. V Příkladu 3 jsme zkoumali řetězec aAbaB. Zkuste sami
říct, zda se jedná o větnou formu gramatiky G nebo ne, tj. dá se aAbaB odvodit
z počátečního neterminálu S?
4
Definice – jazyk generovaný gramatikou
Buď G gramatika nad abecedou Σ. Jazyk generovaný gramatikou G je množina
L(G) = {w ∈ Σ | S ⇒ w}, tj. množina všech slov, které lze odvodit z
počátečního neterminálu S.
Definice – ekvivalence gramatik
Gramatiky G1 a G2 jsou jazykově ekvivalentní, když L(G1) = L(G2), tj. když
generují stejný jazyk.
Příklad 6.
Mějme gramatiku G zadanou takto: G = ({S, A}, {a, b}, P, S), kde P = {
S → aAa | bAb
A → a | b | aA | bA | ε }
Jaká slova generuje gramatika G? Popište přesně jazyk L(G).
Řešení. Vždy nejdříve začneme tím, že si vygenerujeme dostatečně velký počet
slov, abychom pochopili „fungování gramatiky. Sami tedy asi zjistíte, že
L(G) = {aaa, aa, bb, bab, aba, bbb, aaaa, bbbb, baab, babb, . . . }.
Pozornější řešitel si uvědomí fakt, že v 1. kroku každého odvození musíme použít
buď pravidlo S → aAa nebo S → bAb a potom už se k neterminálu S v dalším
odvozování nemůžeme vrátit. Co to znamená? Na začátku i na konci slova jsou
stejné symboly, slovo tedy buď začíná a končí symbolem a nebo začíná a končí
symbolem b.
Větné formy aAa, bAb poté upravujeme tak, že měníme pouze prostřední
neterminál A. Ten můžeme odvozovat libovolným způsobem. Výsledkem tedy
je jazyk
• L(G) = {w ∈ Σ∗
| w = axa ∨ w = bxb, x ∈ {a, b}∗
}
• L(G) obsahuje slova, která začínají a končí stejným symbolem.
Příklad 7.
Navrhněte gramatiky, které budou generovat jazyky
1. L1 = {w ∈ {a, b}∗
| w obsahuje podslovo abb}
2. L2 = {w ∈ {a, b}∗
; |w| = 2k, k ∈ N0}
3. L3 = {w.wR
| w ∈ {a, b}∗
}
5
Řešení.
1. Pro lepší pochopení si neterminály budeme značit jiným způsobem než
jak jsme byli zvyklí. Buď G = ({S, Na, Nab, Nabb}, {a, b}, P, S), kde P = {
S → bS | aNa
Na → aNa | bNab
Nab → aNa | bNabb
Nabb → aNabb | bNabb | a | b | ε }
Všimněte si, že názvy neterminálů uchovávají informaci o tom, v jaké fázi
odvození jsme. V momentě, kdy větná forma obsahuje
• neterminál Na, víme, že je před ním symbol a;
• neterminál Nab, víme, že je před ním podslovo ab;
• neterminál Nabb, víme, že je před ním podslovo abb, tudíž v tuto chvíli
už větná forma obsahuje abb, gramatika může generovat cokoliv a
vždy odvodíme větu – slovo patří do L1.
Podívejme se třeba na odvození slova ababba, které obsahuje podslovo abb:
S ⇒ aNa ⇒ abNab ⇒ abaNa ⇒ ababNab ⇒ ababbNabb ⇒ ababba
2. Jazyk L2 = {ε, aa, ab, ba, bb, aaaa, . . . }. Je tedy nutné, aby se startovní
neterminál S mohl být přepsán na ε. Má-li být délka slova sudá, pak libovolné
slovo vznikne řetězením aa, ab, ba, bb za sebou v libovolném pořadí
libovolně krát. Gramatika G = ({S}, {a, b}, P, S) s pravidly
P = {S → ε | aaS | abS | baS | bbS}
je určitě možným řešením, tj. generuje jazyk L2.
3. Jazyk L3 obsahuje slova jako ε, aa, bb, abba, baab, aaaa, bbbb, . . . Když si
tato slova rozpůlíme: a|a, b|b, ab|ba, ba|ab, aa|aa, bb|bb, zjistíme, že vznikají
„obalováním symbolů z obou stran |. Např. slovo abaaba vznikne tak, že
• symbol | obalíme nejdříve z obou stran a-čkem, tj. a|a,
• poté | obalíme b-čkem: tj ab|ba („obalování probíhá bezprostředně
u symbolu |),
• naposledy | znovu obalíme a-čkem: aba|aba.
Roli | může hrát např. neterminál S, tj. gramatika
G = ({S}, {a, b}, {S → ε | aSa | bSb}, S)
je řešením úkolu, tj. generuje jazyk L3.
6