Gramatyka kontekstowa () – gramatyka formalna, której reguły są postaci:
gdzie: – symbol nieterminalny, – dowolne ciągi symboli terminalnych i nieterminalnych (mogą być puste), – 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 ciągi i 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:
gdzie i są dowolnymi ciągami symboli terminalnych i nieterminalnych spełniającymi warunek:
gdzie oznacza liczbę symboli w ciągu 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.
Kategoria:Języki formalne