GATE CSE 2014 Set 1 | Question: 36

Question

Which of the regular expressions given below represent the following DFA?

1. $0^*1(1+00^*1)^* $
2. $0^*1^*1+11^*0^*1 $
3. $(0+1)^*1$

• A. I and II only
• B. I and III only
• C. II and III only
• D. I, II and III

Comments

how can ardens theorem use here?

---

In 2 they have not covered strings $(10)$*$1$

---

0101 is not possible to genrate by using option (II) so that is not correct regular expression . Here my approach is that try to genrate from 0 length to 3-4 length string for both valid and invalid strings and you will get correct answer 

Answer 1

Correct Option: B

(II) doesn't generate $11011$ which is accepted by the given DFA.

Comments

@ Mk Utkarsh I made mistake while solving , thanks you for correcting me,

---

Can I eliminate option 2 by the following reason.

according to DFA it's 0*11* , but it's given 0*1*1

like this 11*00*1, but it's given 11*0*1.

the transition which remains in same state we can take closure of them, but the transition which transfer the control from one state to another, we've to take them trivially(means only single one)

---

We can also say that, In option(ii), when we start a string with 1 and end with more than one 1, than not accepted by option (ii).

Example:- 1011, 10111, 10111, ....   (1011^+) 

So, option (ii) is incorrect

 

Answer 2

derive regular expression from the given dfa

Comments

Oh sorry Actually i meant

(a+b)*=(a+b)*(a+b)*      ???

---

Yes both are equal..[since both generate sme set of strings. No more no less]

---

For Option (I)     0*1(1+00*1)* = 0*1( ($\varepsilon$+00*)1)* = 0*1(0*1)* = (0*1)+

Is this correct?

Answer 3

0*1*1+ 11*0*1 does not generate 0101 . Hence answer will be option B.

Comments

options were wrongly printed in gateforum material. my bad

Answer 4

The DFA accepts the language “all strings ending with 1”.
So the regular expression corresponding to DFA is (0+1)*1.
Now, by using state elimination method,
So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.
But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.