Context Sensitive Grammar

The Context Sensitive Grammar is formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and non-terminal grammar. It is less general than Unrestricted Grammar and more general than Context Free Grammar.

The context-sensitive grammar was introduced by Noam Chomsky in 1950.





Formal definition of Context-Sensitive Grammar

The formal definition of Context Sensitive Grammar is as follows. It is 4 tuple-

G = (N,Σ,P,S)

N - It is a set of non-terminal symbols,
Σ - It is a set of terminal symbols,
P - It is a set of production rules,
S - It is a start symbol of the production.

It is context sensitive if all the rules in production are in the form -

αAβ → αγβ

where, 

A ∈ N, 

α,β ∈ (N∪Σ)*,

γ ∈ (N∪Σ)+

and, A is non-terminal.



Context Sensitive Language

The language generated by the context-sensitive grammar is called Context Sensitive Language. Context Sensitive Language has the following properties -

  • Union, intersection and concatenation of two context-sensitive languages is context-sensitive.
  • The Kleene plus of a context-sensitive language is context-sensitive.
  • Every context-sensitive language is recursive.
  • Complement of a context-sensitive language is context-sensitive.




Example of Context-Sensitive Grammar

Suppose P is set of rules and a context-sensitive grammar G is -

G = {{S, A,B,C,a,b,c},{a,b,c},P,S}
S -> aSBC
S -> aBC
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc

Then, the language generated by the grammar G is -

{anbncn|n >= 1}