The Gateway to Computer Science Excellence

+34 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

+47 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!

+3

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.

+5

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!

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)

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)

+10 votes

0

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?

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

2.does it generate abab?

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,505 answers

195,556 comments

101,057 users