Gramatyka kontekstowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

\alpha A \beta \rightarrow\,\alpha\,\gamma \beta,

gdzie:

Asymbol 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 \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ą nazywa się 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 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.