Context Sensitive Languages

Productions:	α → β
	α∈ V* N V*
	β ∈ V+
	|α| ≤ |β|

The strings around the N on the left-hand side of the production are the context, so a production works only in a particular context and is therefore context sensitive.

• Context sensitivity seems applicable for some aspects of natural language, e.g., subject-verb agreement.

  	John likes Mary.
  *	John like Mary.

• No effective parsing algorithm is known.

• Parsing is NP-complete, i.e., may take exponential time, requires a search.

• Context sensitive languages are not used much in practice.