Given the following language:
$$
L = \{b^n \mid \text{$n$ is prime} \}\cup \{b^n \mid \text{$n$ is even}\}
$$
Need to proof or disproof whether this language is context-free or not.
I know that only prime numbers is not context-free, but not sure what happens with the following union..any ideas?
Best Answer
We know that if $L_1$ is context-free and $L_2$ is regular, then : $L_1 \cap L_2$ is context-free.
It's easy to see that $\{b^n \mid \text{n is odd}\}$ is regular. ({b}.{bb}*)
Let's assume that $L$ is context-free.
Then $$L \cap \{b^n \mid \text{n is odd}\} = \{b^n \mid n \neq 2 \land\text{n is prime}\}$$ It is easy to show that the resulting language is not context-free (it's the same as without the $n\neq2$.)
There is the contradiction. The resulting language is not context-free. Then $L$ is not context-free.