# Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$.

I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is not a regular language I can use the pumping lemma but I'm unsure about the details.

I also want to prove that $L_2$ is a context free language. Do I need a Push Down Automaton that accepts the language to prove that $L_2$ is a context free language? If so, what would this Push-Down Automaton look like?

## marked as duplicate by Raphael♦Mar 18 '14 at 7:47

While it is possible to show that $L_2$ is not regular using the pumping lemma, it is easier to do so by making use of the fact that the regular languages are close under complement, i.e. a language is regular if and only if its complement is regular.
In order to show that $L_2$ is context-free, you can give either an automaton or a context-free grammar for the language. The automaton is presumably the easier way in this case. Hint: $L_2$ is a deterministic context-free language, so there is a deterministic PDA for $L_2$ that can be derived in a straightforward way from the deterministic PDA of $L_2$'s complement.
• For the context-free part, I thought about creating the PDA for $L_1$ then just turning the accepting states into rejecting states and rejecting states to accepting states. Would this new PDA properly represent $L_2$? – Andrew Reynolds Mar 23 '14 at 8:57