I'm trying to solve the following problem. I am asked to show that $L = \{a^nb^m : m \neq n\}$ is context free by expressing this language $L$ as the union of two other context-free languages.

However, I can't seem to figure out what two context-free languages can be combined via union?!

I know that if I let $L_1=\{a^nb^m : n < m\}$ and $L_2 = \{a^nb^m : n > m\}$, then $L = L_1 \cup L_2$, but how do I go about showing that $L_1$ and $L_2$ are context free? I can't seem to come up with any context free grammars with them. Can anyone give some advice or suggest a different two context free languages to form $L$ via union?


1 Answer 1


You can show that $L_1$ is a context free language because it is produced by the following context-free grammar with starting symbol $S$: $$ S\longrightarrow Sb \text{ } | \text{ }Cb \\ C\longrightarrow \epsilon \text{ } | \text{ }aCb $$

A similar grammar will show that $L_2$ is a context free language.

  • $\begingroup$ Beautiful! Thanks so much! $\endgroup$
    – etnie1031
    Nov 19, 2018 at 17:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .