GATE CSE 1996 | Question: 1.8

Question

Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string).

1. $(00)^ * (\varepsilon +0)$
2. $(00)^*$
3. $0^*$
4. $0(00)^*$

• A. (i) and (ii)
• B. (ii) and (iii)
• C. (i) and (iii)
• D. (iii) and (iv)

Comments

1.)  0^n where n>=0

2.)  0^2n where n>=0

3.)  0^n where n>=0

4.)  0^2n+1 where n>=0

---

basic explanation by taking (00)∗(ε+0) .in it (00)* gives even no of 0's then if i do (00)*epsilon which given also even no of zeros and for (00)*0 gives odd no so totally we can say they given all possible odd and even no's of zeros  and (iii)  0* also gives so c will be answer

---

1. (00)∗(ε+0)(00)∗(ε+0)
2. (00)∗(00)∗
3. 0∗0∗
4. 0(00)∗

please expend all the above options 

---

1- is just 00*(ε+0)

2- is (00)*

3- is 0*

4- is 0(00)*

Answer 1

Answer is C.

You can have any no. of $0$'s as well as null.

A is false because you cannot have single $0$ in ii). same for option B. In D you are forced to have single $0$ in iv) whereas not in iii).

Comments

ii + iv = iii = i.

ii  => all even length.
iv => all odd length.

Note: Epsilon is an even length string whose length is 0.

Answer 2

option c is right.

 

 

Answer 3

i)(00)*(0+ε)

it generates any number of 0's

ii) (00)* 

it generates the only even number of 0's

iii)0*

it generates any number of 0's

iv)0(00)*

it generates the only odd number of zeroes.

So correct option is c i.e. i) and iii) 

Comments

but as R + epsilon is = R so opion A will become (00)* ...????

---

R + epsilon is not R. It is boolean operation i.e. either you take R or you take epsilon.

Answer 4

i) has any number of 0's and iii) has any number of 0's so C is answer