Develop a contextsensitive grammar that generates the langua

Develop a context-sensitive grammar that generates the language  L = { iⁿ j^m kⁿ l^m | n, m 1} Show the derivation of string \"iijjjkklll\" using your CSG grammar.

Solution

The language definiton L={i^n j^n k^m l^m | n,m>=1} means a non-zero number of is followed by the same number of js as there are is,followed by a different non-zero number of ks followed by the same number of ls

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

1. s -> XY

Add rules for generating 1 ij and 1kl:

2. ixj -> ij

3. kyl -> kl

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

4. x -> ixj

5. y -> kyl

For example,a generation chain for iiJJJKKlll is:

->1 xy

->4 ixjy

->4 iixjjy

->2 iijjy

->5 iijjkyl

->5 iijjkkyll

->5 iijjjkkylll

->3 iijjjkklll