show that $L = \{a^n b^m | m\neq n\}$ is context free language

Question

show that $L = \{a^n b^m | m\neq n\}$ is context free language using closure under union

My attempt is

• show L1 = a^n b^m n>m is context free and

• show L2 = a^n b^m n less than m is also context free

Then we know L1 U L2 = {a^n b^m m!=n }is also context free

My question is I dont know how to show L1 and L2 is context free

Answer 1

Try $L_1 = \{ a^n b^n b b^* \}$, $L_2 = \{ a^* a a^n b^n \}$.

It is straightforward to write a CFG for $L_k$, for example:

$L_1 \to A P$, $A \to a | a A$, $P \to \epsilon | a P b$.