Question

A set W of strings of symbols is defined recursively by 1. a, b, and c belong to W. 2. If x belongs to W, so does a(x)c. Which of the following strings belong to W ? a. a(b)c b. a(a(b)c)c c. a(abc)c d. a(a(a(a)c)c)c e. a(aacc)c

Answer 1

a. a(b)c

b. a(a(b)c)c

d. a(a(a(a)c)c)c

Explanation:

We are given the following in the question:

`a,b,c \in W\\\text{If } x \in W \Rightarrow a(x)c \in W`

a. a(b)c

It is given b belongs to W.

`b \in W\\\Rightarrow a(b)c \in W`

b. a(a(b)c)c

`a(b)c \in W\\\Rightarrow a(a(b)c)c \in W`

c. a(abc)c

a(abc)c does not belong to W because we cannot find x in W such that a(abc)c belongs to W.

d. a(a(a(a)c)c)c

`a \in W\\\Rightarrow a(a)c \in W\\\Rightarrow a(a(a)c)c \in W\\\Rightarrow a(a(a(a)c)c)c`

e. a(aacc)c

a(aacc)c does not belong to W because we cannot find x in W such that a(aacc)c belongs to W.