# CFG to generate $L = \{a^{2n}b^n\} \bigcup \{a^mb^{2m}\}$

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.

## 1 Answer

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$

• 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. – Rick Decker Dec 1 '16 at 3:03
• Much better. +1 – Rick Decker Dec 1 '16 at 16:52