0

I have to create a CFG which generates

{a^n (ab)^n c^m d^l e^k | n>0, k, l, m>=0, k<m, m=l+k}

The first part is easy enough, I came up with

S -> aS2abS3 S2 -> aS2ab | epsilon

However, the second part is very confusing. So far I have

S3 -> S4 | epsilon

The problem I have is how do I possibly keep track of all of these variables? K has to be less than m, m has to be equal to l + k, and l must be at least 1 by extension. Can someone give me some general tips for approaching these CFG's?

1
  • In retrospect, that answer went a bit too far, since this is almost certainly homework and you would learn more figuring things out yourself. Here's the tip: PDAs can do palindromes; that's the nature of a stack. So you always have to try to make strings mirror images of one form or another. a^m b^m is a trivial form of mirror iamge (where the mirror turns a's into b's). This one is just a little more complicated, but if you focus on looking for the symmetry, you'll find it.
    – rici
    Nov 4, 2014 at 7:07

1 Answer 1

0

Think inside out (because that's the way CFGs work) and don't get confused by extraneous details.

Here's the tip: CFGs are push-down automata (PDAs) which mean that they have a stack. PDAs are good at symmetry but they can't do antisymmetry. So they can do palindromes, but not repetitions. That's the nature of a stack.

So you always need to look for the mirror images. For example, ambm is a trivial form of mirror iamge, where the mirror turns as into bs.

This one is just a little more complicated, but if you focus on looking for the symmetry, you'll find it.

Having said that, here's the solution:

Since m > l,

cmdlek

can be rewritten as:

cm-lcldlek

And since k = m - l, that's the same as:

ckcldlek

From there it's trivial:

Sinner → cd | c Sinner d
Souter → Sinner | c Souter e
2
  • @ConnerRPanarella: If that's not obvious, try it with pencil and paper. What does Souter produce?
    – rici
    Nov 4, 2014 at 7:13
  • Ah I get it now. This actually isn't homework I'm reviewing for a test and this is a practice question. Nov 4, 2014 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.