edited by
18,680 views
54 votes
54 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
edited by

4 Answers

Best answer
64 votes
64 votes

Correct Option: B

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

edited by
27 votes
27 votes

derive regular expression from the given dfa

1 votes
1 votes
0*1*1+ 11*0*1 does not generate 0101 . Hence answer will be option B.
1 votes
1 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.
Answer:

Related questions

29 votes
29 votes
5 answers
1
go_editor asked Sep 26, 2014
14,770 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\}$...
19 votes
19 votes
4 answers
3
go_editor asked Sep 28, 2014
5,156 views
The function $f(x) =x \sin x$ satisfies the following equation: $$f''(x) + f(x) +t \cos x = 0$$The value of $t$ is______.