# regular language equality prove by induction

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.

## 1 Answer

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).

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