Bezkontextové gramatiky
Bezkontextová gramatika definuje bezkontextový jazyk - jazyk jehož slova se tvoří nezávisle na okolí (na předchozích krocích). Bezkontextovou gramatiku tvoří neterminály (proměnné), terminály (konstanty) a pravidla, které každému neterminálu definují zač je lze přepsat. Jeden neterminál označíme jako startovní, tam začínáme a podle pravidel je dál přepisujeme na výrazy složené z terminálu a neterminálu. Jakmile už není co přepisovat, výraz obsahuje už jen terminály, získali jsme slovo.
Příklad: Bezkontextová gramatika generující početní příklady pro sčítání a násobení do pěti.
S* -> O | ( O )
O -> O+O | O*O | S | 1 | 2 | 3 | 4 | 5
S a C jsou neterminály. S jsme označili * jako startovní neterminál. Číslice, znaménka a závorky jsou terminály (už je nemůžeme přepsat). V gramatice máme definované dvě pravidla (pro každý neterminál jedno), které určují za co lze neterminály přepsat. Jednotlive přepisy jsou oddělené svislou čárou. Touto gramatikou můžeme vygenerovat libovolný početní příklad dle zadání. Zkusme třeba ((1+3)*5)+(3+2)
S -> O+O -> S+S -> (O)+(O) -> (O*O)+(O+O) -> (S*5)+(3+2) -> ((O)*5)+(3+2) -> ((O+O)*5)+(3+2) ->
((1+3)*5)+(3+2)
Derivace slova je odvození slova pomocí gramatiky, tedy záznam postupných přepisů od startovního neterminálu po konečné slovo. Příklad derivace vidíme na konci příkladu. Derivace se podle postupu při přepisování dělí na levou a pravou. Pokud přepisujeme nejprve levé neterminály, jde o levou derivaci. Pokud jedeme zprava jedná se o derivaci pravou.
Derivačni strom je grafické znázornění derivace slova stromem. Pro všechny možné derivace (levou, pravou, moji) by měl derivační strom být stejný. Není-li tomu tak jedná se o nejednoznačnou gramatiku, což je nežádoucí jev.
Definice bezkontextové gramatiky
Bezkontextová gramatika je čtveřice G = (Π,Σ, S, P), kde
Π je konečná množina neterminálů (proměnných)
Σ je konečná množina terminálu (konstant)
S je počáteční neterminál S ∈ Π
P je konečná množina pravidel, přepisů neterminálů na řetězce terminálu a neterminálů
Chomského normální forma - pravidla gramatiky může obsahovat pravidla které se přepisují pouze na terminály, nebo na neterminály (A -> AB | ab). Nesmí tam být pravidlo typu A -> Aa.
Nevypouštějící gramatika - neobsahuje epsilon přechody.