in Theory of Computation edited by
13,378 views
49 votes
49 votes

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$
  1. I and II only
  2. I and III only
  3. II and III only
  4. I, II and III
in Theory of Computation edited by
by
2699 3558 3939
13.4k views

5 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.
0
0

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

1
1

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

34
34
how can ardens theorem use here?
0
0

Subscribe to GO Classes for GATE CSE 2022

4 Answers

59 votes
59 votes
 
Best answer

Correct Option: B

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

edited by
by
2437 3623 5535

5 Comments

mehul vaidya 001 is accepted

1
1

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

0
0
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)
0
0

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

 

1
1
19 votes
19 votes

derive regular expression from the given dfa

by
4 14 27

5 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?
0
0
(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.
2
2
Oh sorry Actually i meant

(a+b)*=(a+b)*(a+b)*      ???
0
0
Yes both are equal..[since both generate sme set of strings. No more no less]
0
0
For Option (I)     0*1(1+00*1)* = 0*1( ($\varepsilon$+00*)1)* = 0*1(0*1)* = (0*1)+

Is this correct?
0
0
0 votes
0 votes
0*1*1+ 11*0*1 does not generate 0101 . Hence answer will be option B.
by
3 7

1 comment

options were wrongly printed in gateforum material. my bad
0
0
0 votes
0 votes
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.
Answer:

Related questions