Gramatyka kontekstowa

Gramatyka kontekstowa

Gramatyka kontekstowa to typ gramatyki formalnej, której reguły mają postać:

• $\backslash alpha\; A\; \backslash beta\; \backslash to\; \backslash alpha\backslash ,\backslash gamma\; \backslash beta$

Gdzie:

• $A$ – symbol nieterminalny,
• $\backslash alpha,\; \backslash beta$ – dowolne ciągi symboli terminalnych i nieterminalnych (mogą być puste),
• $\backslash gamma$ – dowolny niepusty ciąg symboli terminalnych i nieterminalnych.

Każda gramatyka kontekstowa definiuje język kontekstowy, a reguła $A\; \backslash to\; \backslash gamma$ wskazuje, że ciągi $\backslash alpha$ i $\backslash beta$ stanowią kontekst dla zastosowania tej reguły, co tłumaczy nazwę tej klasy gramatyk.

Alternatywna definicja gramatyki kontekstowej, równoważna z wyjątkiem słowa pustego, przedstawia reguły w postaci:

• $\backslash alpha\; \backslash to\; \backslash beta$

Gdzie $\backslash alpha$ i $\backslash beta$ są ciągami symboli spełniającymi warunek:

• $|\backslash alpha|\; \backslash leqslant\; |\backslash beta|$

Tego rodzaju gramatyki określane są jako monotoniczne, ponieważ liczba symboli w procesie wyprowadzania słowa nie maleje.

Gramatyki kontekstowe zostały wprowadzone przez Noama Chomsky’ego w 1950 roku jako formalny sposób opisu języków naturalnych, w których poprawność słowa często zależy od kontekstu jego użycia.

Podsumowanie

Gramatyka kontekstowa to istotny element teorii języków formalnych, definiujący języki kontekstowe poprzez reguły, które uwzględniają kontekst wystąpienia symboli. Wprowadzona przez Chomsky’ego, odgrywa ważną rolę w analizie języków naturalnych.