3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Sep 25, 2015 at 0:24
  • $\begingroup$ Please take a look at my edit. Does it accurately reflect your problem? $\endgroup$
    – D.W.
    Commented Sep 25, 2015 at 4:59
  • $\begingroup$ Yes, thanks for editing. Will keep in mind henceforth. $\endgroup$ Commented Sep 25, 2015 at 6:39
  • 1
    $\begingroup$ Hint: use closure properties. Details are in the question linked by D.W. $\endgroup$
    – Raphael
    Commented Sep 25, 2015 at 6:39
  • $\begingroup$ The easiest proof is using Myhill–Nerode, as you outline. $\endgroup$ Commented Sep 25, 2015 at 8:20

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

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