Question

Find context-sensitive grammars for the following languages:

(a) L = {aⁿbⁿcⁿdⁿ : n≥1}

Answer 1

Context sensitive grammar:

If there exists production a->b

Then a,b belongs to (VuT)⁺

Where V represents variables and T represents Terminals.

Language represented by given grammar= { abcd,aabbccdd,aaabbbcccddd….}

Observations:

Each symbol a,b,c,d should be in same number.

But it should not be zero length string, hence Epsilon not required in the start symbol.

String starts with a and end with d.

Smallest string accepted by grammar is abcd.

Writing grammar by considering above observations:

S->aBSCd | abcd

Ba->aB

dC->Cd

cC->cc

Bb->bb

Verification:

aabbccdd

S->aBSCd

->aBabcdCd

->aaBbcdCd

-> aaBbcCdd

->aaBbccdd

->aabbccdd

Hence given string is accepted.

Variables: S,B,C

terminals: a,b,c,d