Regularity of $w^{|w|}$

65 Views Asked by At

Is it true that for every regular language $L \subseteq \{0,1\}^*$, the language $\{ w^{|w|} \mid w \in L \}$ is also regular?

It seems to me that it is not regular , so I will try to prove it with the pumping lemma. Let the pumping length be $p$ , so we pick the word $(0^p1^p)^{2p}$ , clearly the length of this word is $>p$. Since it is in the form $xy^iz$ for $i\ge0$ , and $|xy|\le p$ , then $y$ is made of $0$'s only , so if $|y| = a > 0$ , then using $i=0$ for the pumping lemma we get $(0^{p-a}1^p)^{2p}$ , now $(2p-a ) \neq 2p$ and that is it. Is my solution correct?

1

There are 1 best solutions below

0
On

Hint. For each language $L \subseteq \{0,1\}^*$, let $f(L) = \{w^{|w|} \mid w \in L \}$. You wonder whether, for every regular language $L$, $f(L)$ is also regular. Since your guess that the answer is negative, you need to find a regular language $L$ such that $f(L)$ is not regular. My hint is that you can take $L = 0^*$, but now you have to prove that $f(0^*)$ is not regular.