Úvod do teoretické informatiky

Bezkontextové gramatiky

Kompletní studijní scripta s vysvětlením, příklady a procvičováním. Vše krok za krokem.

1

Co je to gramatika?

Gramatika je formální způsob, jak popsat (generovat) jazyk — tedy množinu slov. Místo toho, abychom vypisovali každé slovo zvlášť, zapíšeme pravidla, podle nichž se slova sestavují.

💡 Intuice

Představ si, že máš šablonu: „věta = podmět + přísudek". To je pravidlo. Gramatika v teorii jazyků funguje stejně — máš neterminály (zástupné symboly jako „věta", „podmět") a terminály (skutečná písmena/slova). Pravidla říkají, jak neterminály nahradit.

Motivační příklad: aritmetické výrazy

Chceme popsat jazyk plně uzávorkovaných aritmetických výrazů jako:

175    (9+15)    (((10-4)*((1+34)+2))/(3+(-37)))

Abeceda jazyka: Σ = {0,1,2,...,9, +, -, *, /, (, )}

Induktivní definice pomocí pravidel:

D → 0 | 1 | 2 | ... | 9
C → D | DC
E → C | (-E) | (E+E) | (E-E) | (E*E) | (E/E)
D = číslice C = číslo E = výraz
2

Formální definice

Definice — Bezkontextová gramatika

Bezkontextová gramatika je čtveřice G = (Π, Σ, S, P), kde:

  • Π — konečná množina neterminálních symbolů (neterminálů)
  • Σ — konečná množina terminálních symbolů (terminálů), přičemž Π ∩ Σ = ∅
  • S ∈ Π — počáteční neterminál
  • P ⊆ Π × (Π ∪ Σ)* — konečná množina přepisovacích pravidel
Součást Co to je Příklad
Π Neterminály — "zástupné" symboly {A, B, C} nebo {S, E, T}
Σ Terminály — skutečné znaky výsledného slova {a, b} nebo {0..9, +, -, *, /}
S Startovací neterminál — od něj se začíná A nebo S nebo E
P Pravidla tvaru A → α (neterminál → řetězec) A → aBBb, B → ε
⚠️ Klíčový rozdíl od regulárních gramatik

U bezkontextových gramatik může být na pravé straně pravidla cokoliv — libovolný řetězec terminálů a neterminálů. U regulárních gramatik je pravá strana omezena (max. jeden neterminál, vždy na kraji).

„Bezkontextové" = pravidlo A → α lze použít bez ohledu na kontext kolem A.

Notace

Konvence
  • Neterminály: velká písmena A, B, C
  • Terminály: malá písmena a, b, c nebo číslice
  • Řetězce: řecká písmena α, β, γ
  • Pravidlo: A → α (místo (A, α))
Zkrácený zápis pravidel

Více pravidel se stejnou levou stranou:

A → α₁ | α₂ | α₃

Místo tří oddělených pravidel A→α₁, A→α₂, A→α₃.

Příklad gramatiky

G = (Π, Σ, A, P), kde Π = {A, B, C}, Σ = {a, b}, startovní symbol = A:

A → aBBb | AaA
B → ε | bCA
C → AB | a | b
3

Odvozování (derivace)

Definice — Krok derivace (⇒)

Řetězec α lze jedním krokem přepsat na α', tj. α ⇒ α', právě když:

α = β₁Aβ₂ a α' = β₁γβ₂ pro nějaká β₁, β₂, γ ∈ (Π ∪ Σ)* a A ∈ Π, kde (A → γ) ∈ P.

Jinými slovy: vyber jeden neterminál v řetězci, nahraď ho pravou stranou nějakého jeho pravidla.

✅ Příklad kroku derivace

Máme pravidlo B → bCA. Pak:

aCBbA ⇒ aCbCAbA

Neterminál B byl nahrazen řetězcem bCA.

Typy derivací

α ⇒ⁿ α'  = derivace délky n (přesně n kroků)
α ⇒* α'  = derivace libovolné délky (0 nebo více kroků)

Levá a pravá derivace

◀ Levá derivace

V každém kroku nahrazujeme nejlevější neterminál.

E ⇒ E+E ⇒ E*E+E ⇒ a*E+E ⇒ a*a+E ⇒ a*a+a
▶ Pravá derivace

V každém kroku nahrazujeme nejpravější neterminál.

E ⇒ E+E ⇒ E+a ⇒ E*E+a ⇒ E*a+a ⇒ a*a+a

Každému derivačnímu stromu odpovídá právě jedna levá a právě jedna pravá derivace.

Podrobný příklad: generování slova „abbabb"

Gramatika: A → aBBb | AaA,   B → ε | bCA,   C → AB | a | b

0 A
1 ⇒ aBBb [A → aBBb]
2 ⇒ abCABb [B → bCA (první B)]
3 ⇒ abCaBBbBb [A → aBBb]
4 ⇒ abCaBbBb [B → ε (první B)]
5 ⇒ abCabBb [B → ε (B před b)]
6 ⇒ abbaBbBb [C → b]
7 ⇒ abbabBb [B → ε]
8 ⇒ abbabb [B → ε]
4

Derivační strom

Derivace lze znázornit jako strom. Každý derivační strom odpovídá jedné nebo více derivacím (záleží na pořadí nahrazování neterminálů).

Vlastnosti derivačního stromu
  • Kořen je ohodnocen počátečním neterminálem
  • Listy jsou ohodnoceny terminály nebo ε
  • Vnitřní uzly jsou ohodnoceny neterminály
  • Potomci uzlu A jsou symboly pravé strany pravidla A → α
  • Slovo přečteme listovím zleva doprava

Vizualizace derivačního stromu pro „abbabb"

A a B B b b C A ε b a B B ε ε Listy zleva doprava: a · b · b · a · b · b = "abbabb"

Zjednodušená vizualizace — plný strom z přednášky má ještě b jako list pravého B.

5

Jazyk generovaný gramatikou

Definice — Jazyk L(G)

L(G) = { w ∈ Σ* | S ⇒* w }

Jazyk gramatiky G je množina všech slov nad terminální abecedou Σ, která lze odvodit z počátečního neterminálu S.

Definice — Bezkontextový jazyk

Jazyk L je bezkontextový, jestliže existuje bezkontextová gramatika G taková, že L = L(G).

Větné formy

Řetězce α ∈ (Π ∪ Σ)*, pro které platí S ⇒* α, se nazývají větné formy. Jsou to mezikroky derivace (mohou obsahovat neterminály). Slova v L(G) jsou větné formy obsahující jen terminály.

Klasické příklady jazyků a jejich gramatik

L = { aⁿbⁿ | n ≥ 0 } — stejný počet a a b za sebou.

S → ε | aSb

Derivace pro aabb:

S ⇒ aSb ⇒ aaSbb ⇒ aaεbb = aabb
⚠️ Proč ne regulárním automatem?

Jazyk aⁿbⁿ není regulární (dokázáno pumping lemmatem). Bezkontextová gramatika ho ale pěkně zachytí — neterminál S si „pamatuje", kolik a ještě musí přidat b.

L = { w ∈ {a,b}* | w = wᴿ } — všechna palindromy nad {a,b}.

S → ε | a | b | aSa | bSb

Derivace pro abaaaba:

S ⇒ aSa ⇒ abSba ⇒ abaSaba ⇒ abaaaba

Pravidlo aSa „obaluje" S písmenem a z obou stran — zaručuje symetrii.

L = všechna dobře uzávorkovaná slova nad {(, )}. Např. (()())(()) ∈ L, ale )()) ∉ L.

A → ε | (A) | AA
  • ε — prázdné slovo je platné
  • (A) — cokoliv platného zabalené do závorek
  • AA — dvě platné části za sebou

L = aritmetické výrazy s operandy a, operátory + a *, závorky.

E → a | E+E | E*E | (E)

Derivace pro (a+a)*a+(a*a):

E ⇒ E+E ⇒ E*E+E ⇒ (E)*E+E ⇒ (E+E)*E+E ⇒ (a+E)*E+E ⇒ ...
⇒ (a+a)*a+(a*a)
⚠️ Tato gramatika je nejednoznačná!

Výraz a*a+a má dva různé derivační stromy (viz sekce o nejednoznačnosti).

6

Nejednoznačné gramatiky

Definice — Nejednoznačná gramatika

Gramatika G je nejednoznačná, jestliže existuje nějaké slovo w ∈ L(G), kterému přísluší dva různé derivační stromy (resp. dvě různé levé nebo dvě různé pravé derivace).

Příklad: Gramatika E → a | E+E | E*E | (E) je nejednoznačná. Pro slovo a*a+a existují dvě různé levé derivace:

Interpretace 1: (a*a)+a
E ⇒ E+E ⇒ E*E+E ⇒ a*E+E ⇒ a*a+E ⇒ a*a+a

Strom: + je kořen, vlevo a*a, vpravo a

Interpretace 2: a*(a+a)
E ⇒ E*E ⇒ E*E+E ⇒ a*E+E ⇒ a*a+E ⇒ a*a+a

Strom: * je kořen, vlevo a, vpravo a+a

💥 Proč je to problém?

Při parsování programovacích jazyků (překladače) chceme přesně jednu interpretaci. Nejednoznačnost = kompilátor neví, jak výraz vyhodnotit!

Oprava: Jednoznačná gramatika pro výrazy

Místo nejednoznačné gramatiky E → a | E+E | E*E | (E) použijeme:

E → T | T+E
T → F | F*T
F → a | (E)
E = výraz (součty) T = term (součiny) F = faktor (atom)

Tato hierarchie zajišťuje správnou prioritu operátorů (* váže těsněji než +) a gramatika je jednoznačná.

📌 Pozn. — Podstatně nejednoznačná gramatika

Pokud nelze nejednoznačnou gramatiku nahradit žádnou ekvivalentní jednoznačnou gramatikou, říkáme, že je podstatně nejednoznačná.

7

Uzavřenost bezkontextových jazyků

✅ BKJ jsou uzavřeny vůči
  • Zřetězení L₁ · L₂
  • Sjednocení L₁ ∪ L₂
  • Iteraci (Kleene star) L*
❌ BKJ NEJSOU uzavřeny vůči
  • Doplňku (¬L)
  • Průniku L₁ ∩ L₂

Průnik dvou BKJ nemusí být BKJ!

Jak konstruovat gramatiky pro operace

Mějme gramatiky G₁ = (Π₁, Σ, S₁, P₁) a G₂ = (Π₂, Σ, S₂, P₂), kde Π₁ ∩ Π₂ = ∅ a S ∉ Π₁ ∪ Π₂.

Přidáme nový startovní symbol S s pravidlem S → S₁S₂:

G = (Π₁ ∪ Π₂ ∪ {S}, Σ, S, P₁ ∪ P₂ ∪ {S → S₁S₂})

Vygeneruje nejdřív slovo z L(G₁) (přes S₁), pak z L(G₂) (přes S₂).

Přidáme nový startovní symbol S s pravidly S → S₁ a S → S₂:

G = (Π₁ ∪ Π₂ ∪ {S}, Σ, S, P₁ ∪ P₂ ∪ {S → S₁ | S₂})

Z S se dostaneme buď do G₁ nebo do G₂ — tedy vygenerujeme slova z jednoho nebo druhého jazyka.

Přidáme nový startovní symbol S s pravidly S → ε a S → S₁S:

G = (Π₁ ∪ {S}, Σ, S, P₁ ∪ {S → ε | S₁S})

S → S₁S umožňuje opakovat libovolněkrát, S → ε skončí.

8

Regulární gramatiky

Regulární gramatiky jsou speciálním případem bezkontextových gramatik — jejich pravidla jsou omezena na jednodušší formu.

Pravá regulární gramatika

Všechna pravidla jsou tvaru:

A → B
A → aB
A → ε

Neterminál je vždy vpravo.

Levá regulární gramatika

Všechna pravidla jsou tvaru:

A → B
A → Ba
A → ε

Neterminál je vždy vlevo.

Klíčová tvrzení
  • Ke každému regulárnímu jazyku existuje pravá i levá regulární gramatika generující tento jazyk.
  • Ke každé regulární gramatice existuje konečný automat rozpoznávající tentýž jazyk.
  • Tedy: regulární jazyky = jazyky generované regulárními gramatikami = jazyky rozpoznávané KA.

Převod konečného automatu na gramatiku

Existují dva způsoby (levá / pravá gramatika). Každý přechod automatu δ(q, a) = p se zapíše jako pravidlo:

Pravá gramatika z automatu

Přechod A →a B zapíšeme jako:

A → aB

Pro přijímající stavy přidáme: A → ε

Levá gramatika z automatu

Přechod A →a B zapíšeme jako:

B → Aa

Pro počáteční stavy přidáme: A → ε

Obecnější pravidla — lze je rozložit

Někdy se povolují obecnější pravidla tvaru A → wB nebo A → w (kde w ∈ Σ*). Lze je rozložit na elementární pravidla:

Pravidlo A → abbB nahradíme:

A → aX₁    X₁ → bX₂    X₂ → bB

X₁, X₂ jsou nové neterminály použité jen tady.

9

Sbírka příkladů

Otevři každý příklad a zkus si nejdřív sám odpovědět, pak koukni na řešení.

Slova jsou (případně i prázdné) posloupnosti výrazů E oddělených čárkami:

S → T | ε
T → E | E,T
E → ... (definice výrazu jako dříve)

S generuje buď prázdné slovo (ε) nebo neprázdnou posloupnost přes T. T buď jeden výraz, nebo výraz + čárka + další posloupnost.

S → E; | T | if(E)S | if(E)S else S
        | while(E)S | do S while(E); | return F;
T → { U }
U → ε | SU
F → ε | E

S = příkaz, T = blok, U = sekvence příkazů, F = volitelný výraz.

Postup: strom regulárního výrazu, každý uzel dostane neterminál.

S₅ → ε | S₄S₅    (iterace *)
S₄ → S₃S₂    (zřetězení ·)
S₃ → S₁ | S₂    (alternace +)
S₂ → b
S₁ → a
Ekvivalence

G₁ a G₂ jsou ekvivalentní, pokud L(G₁) = L(G₂).

⚠️ Problém ekvivalence je algoritmicky nerozhodnutelný!

Neexistuje algoritmus, který by pro libovolné dvě BK gramatiky rozhodl, zda jsou ekvivalentní. Dokonce je nerozhodnutelné, zda L(G) = Σ*.

10

Kvíz — ověř si znalosti

1. Jakou strukturou formálně popisujeme bezkontextovou gramatiku?
Správně! G = (Π, Σ, S, P) — neterminály, terminály, počáteční neterminál, pravidla.
2. Co znamená zápis α ⇒* β?
Přesně! ⇒* je reflexivní a tranzitivní uzávěr relace ⇒ — derivace 0 nebo více kroků.
3. Gramatika S → ε | aSb generuje jazyk:
Správně! Pravidlo aSb přidá vždy jedno a vlevo a b vpravo, S→ε skončí. Výsledek: stejný počet a a b.
4. Třída bezkontextových jazyků je uzavřena vůči:
Výborně! BKJ jsou uzavřeny vůči zřetězení, sjednocení a iteraci. Průnik a doplněk uzavřenost nezajišťují.
5. Co je levá derivace?
Správně! Každému derivačnímu stromu odpovídá právě jedna levá a právě jedna pravá derivace.
6. Jaká pravidla jsou povolena v pravé regulární gramatice?
Přesně! V pravé regulární gramatice: A→B (epsilon přechod), A→aB (terminál + neterminál vpravo), A→ε (konec).