Gramatyka bezkontekstowa

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

$A\to \mathrm{\Gamma },$

gdzie:

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

$\mathrm{\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|ϵ\},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|ϵ\},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.