Search code examples
programming-languagescomputer-science

Develop a context-sensitive grammar that generates the language


Can some one explain how to create a context-sensitive grammar that generates the language

L={i^n j^n k^m l^m | n,m ≥ 1}?

This is what i got so far:(I'm not sure that it's right)

S → IJ
I → iIX | iX; 
J → jJl | jYl; 
Xj → jX;
XY → Yk;
Y→ε.

I will appreciate if you will explain step by step, how to do it correctly or any path how to check the answer. Because I feel completely lost how to solve these problems even after reading about CFG (CSG) from the book.

Thank you.


Solution

  • The language definition 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 as there are ks.

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

    1. S → XY
    

    Add rules for generating 1 ij and 1 kl:

    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 iijjkkklll is:

    →1 XY
    →4 iXjY
    →4 iiXjjY
    →2 iijjY
    →5 iijjkYl
    →5 iijjkkYll
    →5 iijjkkkYlll
    →3 iijjkkklll