# GATE2014-1-36

9k views

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

edited
0
how state elimination method work here
0
in option 3 after 1, 0 will never generate
0
I THINK ANSWER SHOULD BE "C"

PLEASE GIVE ME SOLUTION SIR ...
0
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.
0

does state elimination method give (1+00*1)*?

27

In this way state elimination method is working here!!!

0
how can ardens theorem use here?

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

edited
11
we can consider like the FSM accepts only strings accepting string ending with 1
0
yes. thats true..
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 !

11
It is hit and trial. You have to check manually. need lot's of practice. 😊
–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

–2
@Arjun Sir 11011 is generated by II) one....
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
also we cant generate 0101 which is accepted by DFA in 2nd case.
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
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.
0
@Anu007 what is b and c?
6
for these type of questions hit and trial does not guarantee success

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.
0
i am not getting excatly why obtion 2 is incorrect?
1

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

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!

1

mehul vaidya 001 is accepted

0

Mk Utkarsh I made mistake while solving , thanks you for correcting me,

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)

derive regular expression from the given dfa

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?
2
(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.
0
Oh sorry Actually i meant

(a+b)*=(a+b)*(a+b)*      ???
0
Yes both are equal..[since both generate sme set of strings. No more no less]
0
For Option (I)     0*1(1+00*1)* = 0*1( ($\varepsilon$+00*)1)* = 0*1(0*1)* = (0*1)+

Is this correct?
0*1*1+ 11*0*1 does not generate 0101 . Hence answer will be option B.
0
options were wrongly printed in gateforum material. my bad
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.

## Related questions

1
5.4k views
Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$? $\{q_0,q_1,q_2\}$ $\{q_0,q_1\}$ $\{q_0,q_1,q_2,q_3\}$ $\{q_3\}$
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.
The function $f(x) =x \sin x$ satisfies the following equation: $f''(x) + f(x) +t \cos x = 0$. The value of $t$ is______.