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

This one was not very easy as tagged.....hit and trial took some time....what we can do in these questions is test both in and not in the language strings...that will help to corner out choices.

---

does state elimination method give (1+00*1)*?

---

In this way state elimination method is working here!!!

---

how can ardens theorem use here?

Answer 1

Correct Option: B

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

Comments

mehul vaidya 001 is accepted

---

@ 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

i have some doubt about regular exp

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

2.does it generate abab?

3.(a+b)* how does string can be written any pattern?

---

(a+b)* not equal to (a+b)(a+b)*.

(a+b)(a+b)* = ${(a+b)^+}$ = (a+b)* -ϵ

(a+b)* generates all the strings over a and b including null string.. ${(a+b)^+}$ will generates all the strings starting with a and b. So both regular expression will generate abab.

---

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.