1

Prove that

$$L=\left\{uvvw\mid u,v,w \in \{a,b,c\}^*\text{ and }v\ne\varepsilon\right\}$$

is not regular a regular language.

Brian M. Scott
  • 616,228
A. Johannson
  • 37
  • 2
    The informal proof goes like this: The finite machine would have to remember the $v$ part and then check to see if it repeats. But since $v$ could be arbitrarily long, that could require more memory than the finite machine has. The formal proof uses the pumping lemma. – MJD May 01 '13 at 13:19
  • 1
    Quick guess: the pumping lemma? – Damian Sobota May 01 '13 at 13:20

1 Answers1

3

Completely revised, and not an answer.

The language $\{a,b,c\}^*\setminus L$ is the language of squarefree words over $\{a,b,c\}$. The link gives two examples of infinite squarefree words over $3$-element alphabets. The obvious idea is to take a long enough squarefree word $w$ and apply the pumping lemma to $ww$, but I don’t see any obvious way to ensure that the shortened word is squarefree. (Clearly the only useful pumping is down.)

Added: I really don’t see how to use the pumping lemma directly. However, the class of regular languages is closed under complementation, and given the existence of arbitrarily long squarefree words over $\{a,b,c\}$, it’s easy to use the pumping lemma to show that the language of squarefree words over $\{a,b,c\}$ is not regular.

Brian M. Scott
  • 616,228
  • 1
    Why is $t\in L$? Did you misread that elements of $L$ have the form $uvvw$, not $uvuw$? – MJD May 01 '13 at 13:25
  • 2
    I tried this several times but no matter what word i choose the lemma always "chooses" a word that can be in the language.... it is completely different from the L={vv∣v∈{a,b,c}∗ and v≠ε} problem, since uv^(p)v^(p)w is from L then however i pump it it always returns a word like uv^(i)v^(i)w=uvvv^(2i-2)w which still is in the language – A. Johannson May 01 '13 at 13:30
  • 2
    @A.Johannson This would have been a useful thing to mention in your original question. – MJD May 01 '13 at 13:33
  • well, the problem is not that easy as it looks at first glance – A. Johannson May 01 '13 at 13:36
  • @MJD: $t\in L$ with $u=\epsilon=w$ and $v=a^{p-1}b$. – Brian M. Scott May 01 '13 at 13:38
  • (like) for the previous comment – A. Johannson May 01 '13 at 13:40
  • @A.Johannson: You’re right: that was an oversight on my part. I’ll think about it for a few minutes and either correct the answer or delete it. – Brian M. Scott May 01 '13 at 13:42
  • well if L(Σ)={a,b}* then L is definately regular and there are two solutions: 1) in Neurode-index R(L)=2, depending on "v"'s length |v|=1 {uaaw, ubbw} and |v|=2 {uababw, ubabaw} and since R(L) is a natural number => L is regular; 2) L={a,b}*{a,b,ab,ba,aba,bab} which is a "subtraction" of a regular language and a finite language => stays regular; – A. Johannson May 01 '13 at 13:55
  • @A.Johannson: Proving that $L$ isn’t regular is going to require (at a minimum) showing that there are arbitrarily long strings over ${a,b,c}$ that aren’t in $L$. – Brian M. Scott May 01 '13 at 14:01
  • exactly! i ve been trying to prove it for 2 days now – A. Johannson May 01 '13 at 14:03
  • To get arbitrarily long strings not in $L$, see http://en.wikipedia.org/wiki/Squarefree_word . Notice also that you'll need to use the pumping lemma with $k=0$ because any word obtained with $k\geq 2$ will automatically be in $L$. Finally, note that in Brian's statement of the pumping lemma, the inequality $|x|\geq p$ should be $|t|\geq p$. – Andreas Blass May 01 '13 at 14:09
  • take a look at this: Let A1=abc, A2=acb, A3=cab, A4=cba, A5=bca, A6=bac.... we can construct the "v"'s as a path in non-oriented graph with V={Ai|1<=i<=6}. I'm sure you can consider the links in G on your own. And now if H is such a path that there is no presentation of HH as XYYZ where (X,Z)!=(0,0) and Y is cycle in G then H is a class of R(L). How to prove that H can be limitless? – A. Johannson May 01 '13 at 14:13
  • @A.Johannson: The language ${a,b,c}^\setminus L$ is the language of [squarefree words*](https://en.wikipedia.org/wiki/Square-free_word) over ${a,b,c}$. The link gives two examples of infinite squarefree words over $3$-element alphabets. (Oops; I see now that Andreas already pointed this out.) – Brian M. Scott May 01 '13 at 14:15
  • @Brian M. Scott, Andreas Blass: Yes, thank you very much! I tried to figure it out on my own but now i see that this actually is a tough problem that was proved by Axel Thue (norwegian mathematician) a long time ago..... Man, that's ridiculous! My proffessors gave to me this problem for homework without telling me anything about the proof or squarefree words or whatever like this... Pathetic Sadists! Thank you once again... See you soon! – A. Johannson May 01 '13 at 14:25