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