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

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

What does $b^n$ mean? What is $m$? – copper.hat May 16 '15 at 02:43 — copper.hat, May 16 '15 at 02:43

copper.hat · Accepted Answer · 2015-05-16T02:54:29.323

0

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$.

edited May 16 '15 at 02:54

answered May 16 '15 at 02:49

copper.hat

This is what I usually say when I am showing a short explanation for multiple choice, Usually I will say L1 equal to that and L2 equal to that, and assume they are both CF, but L1 U L2 is not. – user2247155 May 16 '15 at 02:51
But I don't know how to explain they are CF individually – user2247155 May 16 '15 at 02:52
Write a context free grammar for them. – copper.hat May 16 '15 at 02:52
so as long as I can define a context free grammar, that will be enough to prove that L1 and L2 are both CF?. That should be easy – user2247155 May 16 '15 at 02:56
By definition, a context free language is a language that can be generated by (any suitable) context free grammar. – copper.hat May 16 '15 at 02:57

1 Answers1