5. (20 pts.) For each recursive denition of a set of bit strings below, show 5 e

Question

5. (20 pts.) For each recursive denition of a set of bit strings below, show 5 elements
from each set, and identify what set it is (in a small number of words).
(a) Basis: 1 (epsilon) S1
Recursion: w (epsilon) S1 implies 1w (epsilon) S1.
(b) Basis: 1 (epsilon) S2
Recursion: w (epsilon) S2 implies 0w (epsilon) S2 and 1w (epsilon) S2.
(c) Basis: ? (epsilon) S3
Recursion: w (epsilon) S3 implies 0w1 (epsilon) S3.
(d) Basis: ? (epsilon) S4
Recursion: w 2 S4 implies 0w (epsilon) S4 and w1 2 S4.
(e) Basis: ? (epsilon) S5 and 1 (epsilon) S5
Recursion: w (epsilon) S5 implies w0 (epsilon) S5 and w01 (epsilon) S5

Explanation / Answer

egin{enumerate} item Basis: $1 in S_1$ \ Recursion: $w in S_1$ implies $1w in S_1$. item Basis: $1 in S_2$ \ Recursion: $w in S_2$ implies $0w in S_2$ and $1w in S_2$. item Basis: $lambda in S_3$ \ Recursion: $w in S_3$ implies $0w1 in S_3$. item Basis: $lambda in S_4$ \ Recursion: $w in S_4$ implies $0w in S_4$ and $w1 in S_4$. item Basis: $lambda in S_5$ and $1 in S_5$ \ Recursion: $w in S_5$ implies $w0 in S_5$ and $w01 in S_5$ end{enumerate} end{enumerate} end{document}

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.