According to the given recursive function, are these words in L? Let $\sum = \{0, 1\}$. Define $L$ and $L^{'}$ recursively as follows:


*

*$\lambda \in L$

*if $w \in L$ then $0w \in L$ and $1w \in L^{'}$

*if $w \in L^{'}$ then $0w \in L^{'}$ and $1w \in L$
$\lambda$ is the empty word. And $w$ is a given word.
Are the following words in $L: 0010, 1001, 1110, 0011, 1111, 0000?$

I know the answer is any word that has an even number of $1$s in it is in $L$. But I don't know how to go about determining this.
 A: It is not difficult to translate your question in terms of grammars. The language $L$ is generated by the grammar
\begin{align}
 S &\to 0S + 1T + \lambda \\
 T &\to 0T + 1S
\end{align}
Thus $L$ is the first component of the least solution $(S,T)$ of the system of equations in languages
\begin{align}
 S &= 0S + 1T + \lambda \\
 T &= 0T + 1S
\end{align}
Using Arden's rule, the second equation gives $T = 0^*1S$. The first equation now becomes $S = 0S + 10^*1S + \lambda = (0 + 10^*1)S + \lambda$. Applying again Arden's rule, one gets $S = (0 + 10^*1)^*$, which is exactly the set of words containing an even number of occurrences of $1$'s.
A: We will try and correctly phrase this solution as an induction problem.
We claim that each word with an even number of $1$s is in $L$ and each word with an odd number of $1$s is in $L'$.
To this end, first note that the recursive problem is deterministic and given any word in $0$s and $1$s, we can follow the procedure and find out that it belongs to a set, and only one.
We make an induction on the length ot the words.
We consider as base case $n=0$: the only word, the empty word, has an even $(0)$ number of $1s$ and lies in $L$.
Now, suppose that for some $n \geqslant 0$ the induction hypotheses holds for all words of length $n$.
We show that it's also true for $n+1$, which completes the proof.
Let $w$ be a word of length $n+1$.
We consider four cases:


*

*$w$ has an even number of $1$s and ends in $1$, say it's $w = 1v$.
Then $v$ has an odd number of $1$s and length $n$, so by the induction hypothesis $v\in L'$.
It follows from the recurrence relations $w$ must lie in $L$, which agrees with our induction hypothesis.

*$w$ has an even number of $1$s and ends in $0$, say it's $w = 0v$.
Then $v$ has an even number of $1$s and length $n$, so by the induction hypothesis $v\in L$.
It follows from the recurrence relations $w$ must lie in $L$, which agrees with our induction hypothesis.

*$w$ has an odd number of $1$s and ends in $1$, say it's $w = 1v$.
Then $v$ has an even number of $1$s and length $n$, so by the induction hypothesis $v\in L$.
It follows from the recurrence relations $w$ must lie in $L'$, which agrees with our induction hypothesis.

*$w$ has an odd number of $1$s and ends in $0$, say it's $w = 0v$.
Then $v$ has an odd number of $1$s and length $n$, so by the induction hypothesis $v\in L'$.
It follows from the recurrence relations $w$ must lie in $L'$, which agrees with our induction hypothesis.
This covers all cases and completes the induction.
