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?
Best Answer
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.