Gramatyka kontekstowa

Gramatyka kontekstowa (ang. context-sensitive grammar) – gramatyka formalna, której reguły są postaci:

${\displaystyle \alpha A\beta \to \alpha \,\gamma \beta ,}$

gdzie:

${\displaystyle A}$ – symbol nieterminalny,

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

${\displaystyle \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 ${\displaystyle A\to \gamma ,}$ ciągi ${\displaystyle \alpha }$ i ${\displaystyle \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:

${\displaystyle \alpha \to \beta ,}$

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

${\displaystyle |\alpha |\leqslant |\beta |,}$

gdzie ${\displaystyle |\alpha |}$ oznacza liczbę symboli w ciągu ${\displaystyle \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 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 umieszczone.