Question

A set S of strings of characters is defined recursively by 1. a and b belong to S. 2. If x belongs to S, so does xb. Which of the following strings belong to S? a. a b. ab c. aba d. aaab e. bbbbb

Answer 1

Answer:

a) a

b) ab

e) bbbbb

Step-by-step explanation:

We are given the following in the question:

$a, b \in S$

$x \in S \Rightarrow xb \in S$

a) a

It is given that $a \in S$

b) ab

$\text{If }a \in S\\\Rightarrow ab \in S$

Thus, ab belongs to S.

c) aba

This does not belong to S because we cannot find x for which xb belongs to S.

d) aaab

This does not belong to S because we cannot find x for which xb belongs to S.

e) bbbbb

$\text{If }b \in S\Rightarrow bb \in S\\\text{If }bb \in S\Rightarrow bbb \in S\\\text{If }bbb \in S\Rightarrow bbbb \in S\\\text{If }bbbb \in S\Rightarrow bbbbb \in S$

Thus, bbbbb belongs to S.