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

Answer:

a. a(b)c  

b. a(a(b)c)c  

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

Step-by-step 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.