0

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.

  1. 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.
  2. 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$
  3. 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

Play4u
  • 41
  • 5
  • "On a glance" it should be obvious to you that it has no chance to be regular, because the finite automaton would have to keep track of how many times it had already seen the word, which is a no-go. Better post your pumping lemma proof. Step 3 of your induction is wrong. Actually it is more accurate to say that it is so imprecise that it has no mathematical sense. If you try to formalize it you will see that you get in trouble and it cannot be done. – Michal Adamaszek Sep 14 '20 at 09:36
  • To pin down a specific error, in the end of step 3 you try to use the concatenation, but in fact it is a concatenation together with an extra assumption that the 2nd word is equal to the $n$-th root of the 1st word. – Michal Adamaszek Sep 14 '20 at 09:41
  • @MichalAdamaszek I'm sorry but I don't understand what you mean by "2nd word is equal to the n-th root of the 1st word"". Can you elaborate or provide an example? – Play4u Sep 14 '20 at 09:48
  • 1
    @J.-E.Pin Yes, that's the answer I came up with after the exam – Play4u Sep 14 '20 at 09:56
  • 1
    @MichalAdamaszek You are correct, it can't be done. I've had similar concerns while I was doing the exam but the solution I came up with seemed too convenient and I really didn't have the time for much thinking. As I said the other solution I came up with after ,as it turns out, is correct which sucks :D Anyways thanks for taking your time to answer – Play4u Sep 14 '20 at 10:00

0 Answers0