I want to write a cfg for the following language:

$ L = {((ab)^n)^m }$ $m,n >= 0$

this language produces (abababababab) where:
$n=2, m=3 \\ or \\ n=3, m=2$

I have no idea what to do with it!


No need for a CFG: this language is regular!

$$L = (ab)^*$$

Any number of $ab$s is in the language: just set $n$ to 1, and $m$ to the number of repetitions. So all you need is a Kleene star.

If you really want a CFG, you can do it like this:

$$S \rightarrow SX \mid \varepsilon$$ $$X \rightarrow ab$$

This is the "standard" way of translating a Kleene star into a CFG.

| cite | improve this answer | |
  • $\begingroup$ Knowing this makes the grammar easier but the question about how to write a CFG for this regular (and, therefore, context-free) language remains. $\endgroup$ – David Richerby Mar 21 '19 at 14:55
  • 1
    $\begingroup$ @DavidRicherby Added a translation $\endgroup$ – Draconis Mar 21 '19 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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