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.

---

1. $(0)^* (\epsilon + 0)$  
\[
    \Rightarrow \{ \epsilon, 0, 00, 000, \dots \} = 0^*
\]

2. $(00)^*$  
\[
    \Rightarrow \{ \epsilon, 00, 0000, \dots \}
\]

3. $0^*$  
\[
    \Rightarrow \{ \epsilon, 0, 00, 000, \dots \}
\]

4. $0 (0)^*$  
\[
     \Rightarrow \{ 0, 000, 00000, \dots \}
\]

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

Answer 5

Correct Answer : C

(i)  (00)* (ε+0) → (00)* generates even number of 0’s if it is followed by ε it is of even length only or if it followed by another 0 it becomes of odd length.

Therefore this is 0*

(ii) (00)* → generates string of 0s of even length.

(iii) 0* → It is also same as above (i).

(iv) 0(00)* → Generates string of 0s of odd length.

Therefore, i and iii are equivalent.

Answer 6

PFA the solution in the image attached :