Another more powerful form of grammars is the class of conte

Another more powerful form of grammars is the class of context sensitive grammars which we studied last lecture. They contain rules that have strings on both the left-hand-side and the right-hand-side, as opposed to context-free rules which require a single symbol on the left-hand-side. Consider the following two context sensitive grammars and show what language they will generate (Show the derivations on an example):

I. 1. S aSBC

2. S aBC

3. CB BC

4. aB ab

5. bB bb

6. bC bc

7. cC cc

II. 1. S aAB | aB

2. A aAX | aX

3. B bBd | bYd

4. Xb bX

5. XY Yc

6.Y c

Solution

I. First language generates a language that accepts any string of a\'s followed by equal number b\'s followed by equal number c\'s. E:g aabbcc, aaabbbccc etc

Lets check the grammer

S -> aSBC
-> aaBCBC (S-> aBC)
-> aaBBCC (CB-> BC)
  -> aabBCC (aB -> ab)
  -> aabbCC (bB -> bb)
  -> aabbcc (cC -> cc)

Thus it genertes a string aabbcc

II. Second grammer generates a language that accepts any string of a\'s followed b\'s followed c\'s followed by d\'s with number of a\'s equal to number of c\'s and number of b\'s equal to number of d\'s. E:g aaabbcccdd, aabccd etc.

Lets test

S - > aAB
   -> aaAXB (A-> aAX)
   aaAXbBd (B-> bBd)
   aaaXXbbYdd (A -> aX and B-> bYd)
   aaaXbXbYdd (Xb -> bX)
   aaabXbXYdd   
   aaabbXXYdd
   aaabbXYcdd (XY -> Yc)
   aaabbYccdd
   aaabbcccdd (Y ->c)

Thus aaabbcccdd contains equal a\'s and c\'s and equal b\'s and c\'s