Productions:	&alpha &rarr &beta
	&alpha&isin V* N V*
	&beta &isin V+
	|&alpha| &le |&beta|

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.

Contents    Page-10    Prev    Next    Page+10    Index