1
$\begingroup$

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?

$\endgroup$
1
  • $\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
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for the response. Would L2's complement be L1? $\endgroup$ 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$ 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.