2
$\begingroup$

I want to prove that $L$ is not regular: $$L = \{ww^Rv \mid |w|\ge1 , |v|\ge 0\},$$ where the alphabet contains at least two symbols.

Can someone prove it?

I prefer to use "Pumping Lemma for Regular Languages" to prove it, but I think that's somehow impossible!

Would someone help me, please?

$\endgroup$
  • 1
    $\begingroup$ What is the alphabet? $\endgroup$ – Brian M. Scott Nov 30 '15 at 15:56
  • $\begingroup$ @BrianM.Scott result and proof should be same for any alphabet with > 1 symbol. $\endgroup$ – djechlin Nov 30 '15 at 16:00
  • $\begingroup$ Nonetheless {0,1} is usually implied. $\endgroup$ – djechlin Nov 30 '15 at 16:00
  • $\begingroup$ Yes you need >1 symbol (otherwise $L$ is regular). $\endgroup$ – BrianO Nov 30 '15 at 16:00
  • $\begingroup$ @djechlin: I’m aware that all that matters is that the alphabet have at least two symbols, but the OP may not be. \\ In elementary courses you can’t assume that it’s $\{0,1\}$ even if you know that it’s a two-element alphabet: very often it’s $\{a,b\}$. $\endgroup$ – Brian M. Scott Nov 30 '15 at 16:02
3
$\begingroup$

If the alphabet has only one symbol then $L$ is regular, so assume the alphabet contains at least two symbols, which we'll call $0$ and $1$.

For $n>0$, let $w_n = (01)^n$ and $s_n = w_n w_n^R\in L$. Let $\sim$ be the equivalence relation of the Myhill-Nerode theorem: $$ x\sim y \iff \forall z\,(xz\in L \leftrightarrow yz\in L). $$ By the theorem, $L$ is regular iff $\sim$ has only finitely many equivalence classes.

Suppose $m < n$, and let $z=w_m^R$. We have $w_m z = s_m \in L$. However, if $w_n z = (01)^n(10)^m \in L$, then by definition of $L$ there are $s,t$ with $|s|>0$ such that $$ w_n z = (01)^n(10)^m = (01)^{n-m}(01)^m(10)^m = ss^Rt $$ But because $n>m$, there are no such $s$ and $t$, so $w_n z\notin L$ after all. So this $z$ distinguishes $w_m$ and $w_m$.

It follows that $$ m\ne n \implies w_n \not\sim w_m, $$ so $\sim$ has infinitely many equivalence classes, hence $L$ is not regular.

$\endgroup$
  • $\begingroup$ I cannot add a comment because of my reputation, sorry. But I think the answer of BrianO is not correct, again! Now I think this is incorrect: L0 = L ∩ (01)^+ (10)^+ because 0101101010 is a member of both L and (01)^+ (10)^+ but it's not a member of L0 Again, if I'm wrong, please explain! And Thank you so much for answering me! :) $\endgroup$ – Hsm Nov 30 '15 at 17:32
  • $\begingroup$ This keeps some of the previous answer (the use of $01$ and $10$), but Myhill-Nerode is a much better hammer to hit the problem with. $\endgroup$ – BrianO Nov 30 '15 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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