42 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

53 votes

3

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.

6

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)

13 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?

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.

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.