CMI2017-A-01

Question

The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions:

 

1. $a^*b^*$
2. $(a^*b+b)^*$ 
3. $(a+b^*)^*$
4. $(a^*b)^*$

Comments

i think C

---

Different thought process :) :

option a: after b there can't be a. So eliminated

option b : When we want a, b is compulsory with it. So can't generate single a. eliminated

option d : same as option b, compulsory a b with a. eliminated

Hence option c

Answer 1

(a* + b)* is equivalent to:

- $\text{(a + b)*}$

- $\text{(a + b*)*}$

- $\text{(a*b*)*}$

- basically any regular expression which can generate all strings in $\Sigma^*$.

Now looking at the options:

(a) $\text{a*b*}$ - This can't generate abab

(b) $\text{(a*b+b)*}$ - This can't generate aaa (at least one b needs to be there in any non-empty string)

(c) $\text{(a+b*)*}$ - This one can generate all strings, i.e it is equivalent to (a+b)*

(d) $\text{(a*b)*}$ - This can't generate aaa (at least one b needs to be there in any non-empty string)

So, correct option should be (C) (a+b*)*.

Answer 2

A, No a can be there once we have b. ba not accepted.

B. Every a must be followed by b. a not accepted.

D. Every a must be followed by b. a not accepted.

C is correct.

(a* + b)* is equivalent to:

- (a + b)*

- (a + b*)*

- (a*b*)*

- (b*a*)*

- (a* + b*)*

- a*(ba*)*

- b*(ab*)*

Answer 3