let $L\subseteq\{0,1\}^*$ be declared by the following conditions:

a. $0, 01\in L$.

b. if $w_1,w_2\in L$ so $w_1\cdot w_2\in L$.

c. if $w\cdot 0\in L$ so $w \in L$.

prove that $L=\{w| w=\epsilon\: or \: w\in 0\cdot (0,1)^* \wedge not \: contains \: 11\: as \: substring \}$

conclude that $L$ is a regular language.

I tried to prove the first side of the equality using induction but I am stuck in the step of the induction. I tried to take a word of size $n+1$ but I am not sure how to devide the word.

I would like to get assist also with the second part of the equality that I am not sure how to prove.


I think it is most straightforward to prove both inclusions by induction. Namely, let $M$ be the language described by the condition you have above; we wish to show that $L \subseteq M$ and $M \subseteq L$.

For $L \subseteq M$, we will actually use structural induction, rather than induction on the length of the string. What this means is that we will induct on the fact that the string is in $L$ because it satisfies some part of the definition above, i.e it is built from strings we already know are in $L$; we then show that, assuming these strings are in $M$, so too is the string constructed from them.

It is clear that $0, 01 \in M$. So we have our base cases, and proceed with the inductive cases.

Let $w = w_1 \cdot w_2$ where $w_1, w_2 \in L$. By induction hypothesis, this means that $w_1, w_2 \in M$. It follows that neither of them contains a $11$ and both begin with $0$. Then $w$ also begins with $0$, and it does not contain a $11$ -- the only possible place this could happen is from the last character of $w_1$ and the first one of $w_2$, but $w_2$ begins with $0$. Thus, $w \in M$.

Now let $w \cdot 0 = w'$ where $w' \in L$. By induction hypothesis, $w' \in M$, so it begins with $0$; so too must $w$. Additionally, $w$ cannot contain a $11$, as this would mean $w'$ does as well. Thus, $w \in M$. (Actually we have to be a little careful here to consider the case where $w = \epsilon$ separately, but you can do this case explicitly).

This proves the inclusion $L \subseteq M$. For the other direction, we proceed by strong induction on the length of the string. Base cases should be $\epsilon, 0$; the inclusion of both of these in $L$ is straightforward.

Let $w \in M$ have length at least $2$. It must end in a $0$ or a $1$. If it ends in a $0$, then let $w = w' \cdot 0$. Since $w \in M$, it must begin with a $0$ and not contain $11$; then $w'$ does as well, so $w' \in M$. But by induction hypothesis, this means $w' \in L$, and $w = w' \cdot 0$, both of which are in $L$; then $w \in L$.

If $w$ ends in a $1$, then we know that it must end in $01$ (it has length at least $2$ and cannot end in $11$). The same argument as before, taking $w = w' \cdot 01$ suffices (this is why we need strong induction, or at least must consider all strings of length up to $n-2$ as well).

  • $\begingroup$ It is the first time I uses structrual induction. can you tell me how the hypothesis gonna be? $\endgroup$ – UltimateMath Dec 10 '18 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.