This question already has an answer here:

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Since you did not include any attempt of your own, this is a duplicate of our reference question(s). The first one I used for closing, the reference for the second question is this, if not as extensively answered. $\endgroup$ – Raphael Mar 18 '14 at 7:49

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.

  • $\begingroup$ Thanks for the response. Would L2's complement be L1? $\endgroup$ – Andrew Reynolds Mar 17 '14 at 23:56
  • 1
    $\begingroup$ yes, it would.. $\endgroup$ – FrankW Mar 18 '14 at 0:00
  • $\begingroup$ 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$? $\endgroup$ – Andrew Reynolds Mar 23 '14 at 8:57
  • 1
    $\begingroup$ It would, if it is deterministic. $\endgroup$ – FrankW Mar 23 '14 at 10:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.