Bezkontextové gramatiky
Definice – bezkontextová gramatika
Bezkontextová gramatika (zkráceně CFG – Context Free Grammar) je čtveřice
(N, Σ, P, S) taková, že:
• N je množina neterminálů;
• Σ je množina terminálů, pro kterou platí N ∩ Σ = ∅;
• P ⊆ N × (N ∪ Σ)∗
je množina pravidel;
• S je startovní (počáteční) neterminál.
Poznámka.
Všimněte si dvou věcí:
1. množiny N, Σ mají prázdný průnik, tj. nemůžeme se stát, že by nějaký
symbol byl zároveň neterminál i terminál.
2. Množina pravidel P je definována jako podmnožina kartézského součinu,
tj. je to relace mezi množinami N a (N ∪ Σ)∗
. Znamená to, že levá strana
pravidel je vždy jen jeden neterminál a pravá strana může být cokoliv,
dokonce i prázdné slovo ε.
Poznámka.
V bodu 2. předchozí poznámky jste možná postřehli rozpor mezi naší aktuální
definicí bezkontextové gramatiky a definicí uvedenou v Chomského hierarchii
gramatik. Zde se za bezkontextovou gramatiku považuje taková gramatika G =
(N, Σ, P, S), kde libovolné pravidlo z P je tvaru A → β, kde
• A ∈ N,
• β ∈ (N ∪ Σ)∗
,
• |β| ≥ 1
s eventuální výjimkou S → ε, pokud se S nevyskytuje na pravé straně žádného
jiného pravidla.
Všimněte si, že v definici uvedené na začátku tohoto textu chybí 3. podmínka
|β| ≥ 1, tj. můžeme libovolný neterminál odvodit na prázdné slovo. V kapitole 9
si ukážeme, že tento rozdíl není podstatný – každé pravidlo A → ε, kde A ∈ N,
dokážeme odstranit a nahradit jinými pravidly tak, aby se jazyk generovaný
gramatikou nezměnil.
1
Příklad 1.
Určete jazyk L = L(G), který generuje gramatika G = ({S}, {a, b}, P, S), kde
P = {S → aSb | aSb | ab}.
Řešení. Gramatika generuje jazyk L = {w ∈ {a, b}∗
| an
bn
, n ≥ 1}.
Příklad 2.
Určete jazyk L = L(G), který generuje gramatika G = ({S}, {a, b}, P, S), kde
P = {S → aSa | bSb | aa | bb}.
Řešení. Gramatika generuje jazyk
L = {abba, aa, bb, abbbbbba, . . . } = {w.wR
, w ∈ {a, b}+
}.
Příklad 3.
Navrhněte bezkontextovou gramatiku G, která akceptuje jazyk
L = {w ∈ {a, b}∗
, #a(w) = #b(w)}.
Řešení. G = ({S, T, A, B}, {a, b}, P, S), kde
P = {S → ε | abS | baS | aaSBS | bbSAS,
A → aa,
B → bb}
2