Context Sensitive Grammar and Language

In this class, We discuss Context Sensitive Grammar and Language.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of context-free grammar. Click Here.

In our previous classes, we discussed regular grammar.

The language aⁿbⁿ can not be defined using regular grammar.

Similarly, the language aⁿbⁿcⁿ can not be defined using a context-free grammar.

Yes, we can define the language aⁿbⁿcⁿ using context-sensitive grammar.

Given grammar G = (V, T, P, S)

The production conditions are different from regular and context-free grammar.

Production Conditions:

1) Take a production X – Y

X, Y belongs to (V U T)^+

X, Y is a string of terminals and non-terminals.

The symbol + says atleast one symbol considered.

From the first condition, we understand epsilon is not present in the production.

Context-sensitive grammar does not allow epsilon in the language.

2) |X| <= |Y|

The length of the left side production should be less than or equal to the length of the right side of the production.

Example: aAb – abb

aAc – abcD

aA – c

The last production is not context-sensitive grammar because the length of the left side is greater.

Why is the name context sensitive?

Example:

aAb – aaa

aA – b

We are applying A based on the Context.

We define the production Based on the before and after symbol.

If the before symbol is a and the after symbol is b, we apply aaa.

We do not consider the Context in a context-free grammar.

A – aA | aB

Whenever we see production A, we apply.

CFG is a subset of context-sensitive grammar.

Assumption: epsilon not in language.

The production condition of CFG is one condition in Context-sensitive grammar.

The below Venn diagram shows the acceptance of languages.