Context-sensitive grammar for specific language

Question

How can I construct a grammar that generates this language? Construct a grammar that generates L:

L = {a^n b^m c^k|k>n, k>m}

I believe my productions should go along this lines:

S-> ABCC
A-> a|aBC|BC
B-> b|bBC
C-> c|Cc
CB->BC

The idea is to start with 2 c and keep always one more c, and then with C->c|Cc ad as much c as i want. How can my production for C remember the numbers of m and n.

Answer 1

One option would be the following: generate a string in which every time you generate a c, you either

• don't generate anything else,
• generate an a to pair it with,
• generate a b to pair it with, or
• generate an a and a b to pair it with.

This starts off here:

S → X

X → c | MXc | Xc

M → A | B | AB

Bc → bc

Ab → ab

BA → AB

(Note that this is partially incomplete). Here, X expands out to a series of c's on one side of the string that are paired on the other side of the string with As and Bs. The productions for As and Bs are there to ensure that they're reordered into the proper order before being expanded.

One case this doesn't consider is what happens if you have a string of the form aⁿc^n+k, but that can be fixed as follows:

S → X | Y

X → c | MXc | Xc

M → A | B | AB

Bc → bc

Ab → ab

BA → AB

Y → aYc | Yc | c

Hope this helps!