Vrftsjtryk

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

a. $0, 01in L$.

b. if $w_1,w_2in L$ so $w_1cdot w_2in L$.

c. if $wcdot 0in L$ so $w in L$.

prove that $L={w| w=epsilon: or : win 0cdot (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).