Develop a contextsensitive grammar that generates the langua

Develop a context-sensitive grammar that generates the language L = { in jm kn lm | n, m 1} Show the derivation of string \"iijjjkklll\" using your CSG grammar.

Solution

The language definition L = {i^n j^m k^n l^m | n,m > 1} means a non-zero number of i\'s followed by the same number of k\'s as there are i\'s, followed by a different non-zero number of j\'s followed by the same number of l\'s as there are j\'ss.

So, start with a starting rule to generate the two independent parts of the language:

S -> XY

Add rules for generating 1 ik and 1 jl ;

1. iXk -> ik

2. jYl -> jl

Add rules for generating multiple \'nested\' sets:

4. X -> iXk

5. Y -> jYl

For example, a generation chain for iijjjkklll is:

Hence given string derivation has been proved

      1 XY  4 iXkY  4 iiXkkY  2 iikkY  5 iikkjYl  5 iikkjjYll  5 iikkjjjYlll  3 iikkjjjlll