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.
The language definition L={i^n j^n k^m l^m | n,m ≥ 1}
means a non-zero number of i
s followed by the same number of j
s as there are i
s, followed by a different non-zero number of k
s followed by the same number of l
s as there are k
s.
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