Gramatyka bezkontekstowa

Gramatyka bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:

$A\to \Gamma ,$

gdzie:

$A$ – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje;

$\Gamma$ – dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.

Formalna definicja

Gramatyką bezkontekstową nazywa się czwórkę uporządkowaną $(T,N,P,S),$ gdzie:

• $T$ jest skończonym zbiorem symboli terminalnych,
• $N$ jest skończonym zbiorem symboli nieterminalnych,
• $P$ jest skończonym zbiorem reguł typu $L\to R,$ gdzie $L\in N$ oraz $R\in (T\cup N)^{*},$
• $S\in N$ jest wyróżnionym elementem początkowym.

Przykłady

Przykład 1

Gramatyka $(\{a,b\},\{S\},\{S\to aSb|\epsilon \},S)$ generuje język $\{a^{n}b^{n}:n\in \mathbb {N} \}.$ Ten język nie jest regularny.

Przykład 2

Język $\{w:w\in \{a,b\}^{*}\wedge w=w^{R}\},$ który jest językiem wszystkich palindromów nad alfabetem $\{a,b\},$ może być wygenerowany przez następującą gramatykę:

$(\{a,b\},\{S\},\{S\to aSa|bSb|a|b|\epsilon \},S).$

Postaci normalne

Każdy język bezkontekstowy nie zawierający słowa pustego może być wyrażony za pomocą gramatyki w postaci normalnej Greibach oraz postaci normalnej Chomskiego.