Gramatyka kontekstowa

Gramatyka kontekstowa (Szablon:Ang.) – gramatyka formalna, której reguły są postaci:

$\alpha A\beta \to \alpha \gamma \beta ,$

gdzie:

$A$ – symbol nieterminalny,

$\alpha ,$ $\beta$ – dowolne ciągi symboli terminalnych i nieterminalnych (mogą być puste),

$\gamma$ – dowolny niepusty ciąg symboli terminalnych i nieterminalnych.

Każda gramatyka kontekstowa definiuje pewien język kontekstowy. Należy zwrócić uwagę, że właściwa reguła to $A\to \gamma ,$ ciągi $\alpha$ i $\beta$ stanowią kontekst, w którym dopuszczalne jest zastosowanie tej reguły, stąd właśnie pochodzi nazwa tej klasy gramatyk.

Funkcjonuje również równoważna (z dokładnością do słowa pustego) definicja gramatyki kontekstowej: gramatyką kontekstową nazywa się gramatykę, której reguły są postaci:

$\alpha \to \beta ,$

gdzie $\alpha$ i $\beta$ są dowolnymi ciągami symboli terminalnych i nieterminalnych spełniającymi warunek:

$|\alpha |⩽|\beta |,$

gdzie $|\alpha |$ oznacza liczbę symboli w ciągu $\alpha .$ Takie gramatyki nazywa się też gramatykami monotonicznymi z uwagi na to, że liczba symboli podczas wyprowadzania słowa nigdy nie maleje.

Gramatyki kontekstowe zostały wprowadzone przez Noama Chomskiego w roku 1950 jako sposób formalnego opisu języków naturalnych, w których często poprawność wystąpienia słowa zależy od kontekstu, w którym jest ono umieszczone.