I've been struggling to find the grammar to generate the language

$$L = \{a^{2n}b^n : n \text{ is natural}\} \cup \{a^mb^{2m} : m \text{ is natural}\}.$$

I've considered

$$S \to aS|Sb|ab,$$

which works in some cases, but not all (we can derive $a^{k}b$ for example).

What considerations am I not taking into account? There first is the requirement that in a degenerate case we generate $abb$ or $aab$, and there's the consideration that we need to double the number of respective symbols each time.

A promising alternative seems to be

$$S \to aSb|a|b,$$

which balances the left and right sides such that one is always greater than the other by one, but not by a factor of two.


In this case you have the union of two trivially CGF languages and usually that is achived by the following trick. You write some $S_1$ grammar for the first one, $S_2$ grammar for the second one and just "or" them somewhere at the top level (here it's $S$). Your approach was just to use single recurrent literal, if I can say like that, and thus it was difficult to come up with CGF rules.

You would get something like this:

$S \to S_1 | S_2 $
$S_1 \to a^2 S_1 b | a^2 b$
$S_2 \to a S_2 b^2 | a b^2$

  • 2
    $\begingroup$ Correct, but perhaps a few more words of explanation would help the OP to see the principles behind what you're doing. As one of our mods sometime says, you've given the OP a fish; better would be to give instruction on how to fish. $\endgroup$ – Rick Decker Dec 1 '16 at 3:03
  • $\begingroup$ Much better. +1 $\endgroup$ – Rick Decker Dec 1 '16 at 16:52

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.