We have to give the recursive definition of the set of bit strings of even length that start with 1
We were shown an example that showed the set of all bit strings with no more than a single 1 can be defined as:
Intitial Condition: $(\gamma, 1 \in S)$
Recursion: If $w\in$ S, then $0w \in$ S and $w0 \in$ S.
Do I apply the same method for the question posed above?
Best Answer
Yes, you use the same idea, but of course you have to adapt the definition so you only get exactly those bit strings that are of even length and start with 1. Given these requirements, the initial condition becomes $$10, 11 \in S.$$ For the recursive step, you have to make sure that you always append an even number of bits at the end of string. In this case, there are four substrings you can append to the string while still keeping the length of the string even. $$\text{If } w \in S, \text{ then } w10 \in S, w11 \in S, w00 \in S, w01 \in S.$$