I had an exam where I had to prove or disprove that the language $L=\{w^{|w|} | w \in \Sigma^*\}$ where $\Sigma = \{0,1\}$ is regular.
On a glance, it looked regular to me so I tried using induction to prove that it is in fact, regular. Here's what I did:
Let $|w|=n$. We will use induction over $n$ to prove $L$ is regular.
- Base: Let $n=1$. Then we have $|w|=1$, so $w$ is made up of one letter (either 0 or 1) and $L = w^1=\{0,1\}$. Then $L$ is finite and therefore regular.
- Hypothesis: Let's assume that our claim is true and $L$ is regular for a given $n$ (that is $L=\{w^n\}$ is regular). We will now try to prove that $L$ is regular for $n+1$
- Step: If $|w|=n+1$, then $L=\{w^{n+1}\}=\{w^n.w\}$. From our hypothesis we get that $w^n$ is regular. Since our $n$ is not infinite we know that $w$ is finite and as such there exists a regular expression that recognizes $w$. Which means that $w$ is regular as well. Now we have that $L=\{w^n.w\}$ is a concatenation of two regular languages which means that L is regular as well.
I had 0 points given for that answer. Unfortunately we are not allowed to see our mistakes or possible solutions as that problem was a part of the graduation exam in my country so I have no idea where I got wrong. I would greatly appreciate if you could point where I've made a mistake and point me to a possible solution.
P.S. After the exam I came up with something proving that the language is not regular using the pumping lemma but I will probably post it a bit later