How to prove that given language is not regular?

100 Views Asked by At

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.

1

There are 1 best solutions below

14
On

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.