Gramatyka kontekstowa

Gramatyką kontekstową (and. context-sensitive grammar) – gramatyka formalna, której reguły są postaci:

$\alpha A \beta \rightarrow \alpha \gamma \beta$

gdzie $A$ jest symbolem nieterminalnym, $\alpha$, $\beta$; są dowolnymi ciągami symboli terminalnych i nieterminalnych (mogą być puste), natomiast $\gamma$ to dowolny niepusty ciąg symboli terminalnych i nieterminalnych. Każda gramatyka kontekstowa definiuje pewien język kontekstowy.

Zauważmy, że właściwa reguła to $A \rightarrow \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ą nazywamy gramatykę, której reguły są postaci:

$\alpha \rightarrow \beta$

gdzie $\alpha$ i $\beta$ są dowolnymi ciągami symboli terminalnych i nieterminalnych spełniającymi warunek: $|\alpha| \leqslant |\beta|$, gdzie $|\alpha|$ oznacza liczbę symboli w ciągu $\alpha$. Takie gramatyki nazywamy też gramatykami monotonicznymi z uwagi na to, że liczba symboli podczas wyprowadzania słowa nigdy nie maleje.

Gramatyki kontekstowe zostały wprowadzone przez Noama Chomsky'ego 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 umieszone.