According to the given recursive function, are these words in L?

Question

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.

Answer 1

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.

Answer 2

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.