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?


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 '18 at 17: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.