The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+27 votes

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

- $0^*1(1+00^*1)^* $
- $0^*1^*1+11^*0^*1 $
- $(0+1)^*1$

- I and II only
- I and III only
- II and III only
- I, II and III

+39 votes

+2

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 !

I am right now confused with the above arguement in mind ! Please help !

–1

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

0

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!

+2

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

0

@arjun sir, how to approach these type of questions? Hit and trail method is taking lot of time and doesnot guarantee correct answer too.

0

- 0*1(1+00*1)*= this is ture b/c end with any number of 1.
- 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.
- (0+1)*1= this is ture b/c end with any number of 1.

+3

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.

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.

+1

neha singh create a DFA for just 11^{∗}0^{∗}1 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

0

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!

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,009 questions

45,506 answers

131,660 comments

48,693 users