Problem
For these recursive definitions of sets of bit strings, show 5 elements from each set, and identify what set it is (in a few words).
Attempt
1
- Basis: $1 \in S_!$
- Recursion: $\omega \in S_1 \rightarrow 1\omega \in S_1$
- Five Elements: $1, 11, 111, 1111, 11111$
- Description: A string of 1's from length 1 to infinity.
2
- Basis: $1 \in S_2$
- Recursion: $\omega \in S_2 \rightarrow 0\omega \in S_2 \wedge 1\omega \in S_2$
- Five Elements: 1, 01, 11, 001, 101, 011, 111, ...
- Description: A string of 0's and 1's from length 1 to infinity, not ending in 0.
No idea how to do the following. What is $\lambda$?
3
- Basis: $\lambda \in S_3$
- Recursion: $\omega \in S_3 \implies 0\omega1 ∈ S_3$
4
- Basis: $\lambda \in S_4$
- Recursion: $\omega \in S_4 \implies 0\omega \in S_4 \land \omega1 \in S_4$
5
- Basis: $\lambda \in S_5 \land 1 \in S_5$
- Recursion: $\omega ∈ S_5 \implies \omega0 \in S_5 \land \omega01 \in S_5$
My book didn't even cover this topic, neither did the prof. cover it in class.
Will someone please:
- Verify if I wrote the descriptions for 1 and 2 correct (and provide an example if incorrect)?
- Tell me the meaning of $\lambda$?
- And give examples of how to interpret / solve 3 through 5?
In this context, $\lambda$ denotes the empty string, namely the string with no characters. For your question (3), then, we have $\lambda\in S_3$ so concatenating a $0$ on the left and $1$ on the right (of nothing) yields $01\in S_3$. Questions (4) and (5) are done similarly.
Your first two solutions are correct.
Added. By the way, a fair number of authors use $\epsilon$ instead of $\lambda$.