This question already has an answer here:

Consider the non-regular language $L_1$ = {$a^n$b$a^n$: $n \geq 0$} and its super-set language

L = Language of strings with equal number of trailing and leading a's,

or in other words,

$$L = \{a^n b w b a^n : n \ge 0, w \in \{a,b\}^*\} \cup \{a^n b a^n : n \ge 0\}.$$

How would we prove that L is also non-regular?

I have the idea that I should use the help of $L_2 = L - L_1$, but I'm stuck at the following step:

$L_1 \cap L_2 = \phi $ , thus $L_1 \cap L_2$ is a regular language.

I was trying to prove it using contradiction.

Let, L to be regular which is $L_1 \cup L_2 $ is regular.

And tried to prove, $L_1$ or $L_2$ is equal to a set union or intersection or complement operation over the regular sets $L_1 \cap L_2 $ and $L_1 \cup L_2$

But stuck at

$L_1 = [(L_1 \cup L_2) \cap (L_2)^c] \cup (L_1 \cap L_2)$

With Myhill-Nerode theorem: I might be incorrect please fix me if I am wrong.

Take S =$a^*(b+b.(a+b)^*.b)$
Pick x and y from S such that $x \neq y$.

x = $a^n b$
y = $a^m b$
Take, z = $a^n$

$x.z \in L$ but $y.z \notin L$. Thus, by Myhill_Nerode one can conclude it to be non-regular.

marked as duplicate by David Richerby, Community Sep 25 '15 at 14:13

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.

  • 1
    1. It's not clear to me what your language $L$ is. Please edit. I'll put this on hold to give you a chance to clarify. 2. Isn't this already covered by cs.stackexchange.com/q/1031/755? Is there a reason this is not a duplicate? 3. What have you tried? Have you tried the techniques listed there? We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it'd be helpful if you wrote your thoughts and what you could not figure out. We're not here to solve your exercises for you. – D.W. Sep 25 '15 at 0:24
  • Please take a look at my edit. Does it accurately reflect your problem? – D.W. Sep 25 '15 at 4:59
  • Yes, thanks for editing. Will keep in mind henceforth. – letsBeePolite Sep 25 '15 at 6:39
  • 1
    Hint: use closure properties. Details are in the question linked by D.W. – Raphael Sep 25 '15 at 6:39
  • The easiest proof is using Myhill–Nerode, as you outline. – Yuval Filmus Sep 25 '15 at 8:20
up vote 5 down vote accepted

Since you already know that $L_1$ is nonregular, here is a simple proof. Suppose that $L$ is regular. Then since $a^*ba^*$ is regular, the language $L \cap a^*ba^*$ should be regular. But $L \cap a^*ba^* = L_1$, which is not regular. Hence $L$ is nonregular.

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