The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 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
asked in Theory of Computation by Veteran (99.8k points)
edited by | 2.6k 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?

2 Answers

+39 votes
Best answer

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

answered by Veteran (355k 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.yessmiley


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!

0 votes

derive regular expression from the given dfa

answered by Junior (687 points)

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

38,009 questions
45,506 answers
48,693 users