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 ab
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 A
s and B
s. The productions for A
s and B
s 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 ancn+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!