The Gateway to Computer Science Excellence
+39 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 by Veteran (105k points)
edited by | 4.5k views
how state elimination method work here
in option 3 after 1, 0 will never generate

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?

3 Answers

+51 votes
Best answer

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

by Veteran (431k points)
edited by
we can consider like the FSM accepts only strings accepting string ending with 1
yes. thats true..
11011 is not generated by the RE , so , is there any method to come up with the exact string like 11011 ,  that violated (II) ? There can be so many possibilities and all three REs seem to produce strings which ends in 1 !

I am right now confused with the above arguement in mind ! Please help !
It is hit and trial. You have to check manually. need lot's of practice. 😊

11011 can be obtained by II)

Here's how 11 can be generated from 11*0*1 then 01 can be generated from 0*1*1 and finally the last 1 can be generated from 0*1*1

@Arjun Sir

Please correct me if I am not evaluating the R.E the right way

@Arjun Sir 11011 is generated by II) one....

What is I take like this (0∗1∗1+11∗0∗1)* ?

Now ,it will aceept the language!

I made this mistake, I took like this for 11011

1(0*1*1),1(0*1*1),011(0*1*1) but here I used expression 3 times which is not accepteble!

Option (II) does not accept string 1011 (of length 4) as well , which is accepted by the DFA and the other two options(I and III).
also we cant generate 0101 which is accepted by DFA in 2nd case.
@arjun sir, how to approach these type of questions? Hit and trail method is taking lot of time and doesnot guarantee correct answer too.
  1. 0*1(1+00*1)*= this is ture b/c end with any number of 1.
  2. 0*1*1+11*0*1= here restriction is when if start with 1 then if 0 comes then end with single 1 but DFA does not say this. so false.
  3. (0+1)*1= this is ture b/c end with any number of 1.
@Anu007 what is b and c?
for these type of questions hit and trial does not guarantee success

Follow these steps

1) Create dfa's from reg ex

2) minimize the DFA's

the minimized DFA must be same for all regular expression if all the regular expressions are equivalent.
i am not getting excatly why obtion 2 is incorrect?

neha singh create a DFA for just 1101 you can check that if a string is starting with 1 then sub string 011 leads to trap state but the given DFA accept 1011


 smartmeet what is the reason?

1(0*1*1),1(0*1*1),011(0*1*1) but here I used expression 3 times which is not accepteble!


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)
+11 votes

derive regular expression from the given dfa

by Active (1.1k points)
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]
0 votes
0*1*1+ 11*0*1 does not generate 0101 . Hence answer will be option B.
by (385 points)
options were wrongly printed in gateforum material. my bad

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,296 answers
104,974 users