edited by
10,720 views
36 votes
36 votes

A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below.

Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?





edited by

6 Answers

Best answer
46 votes
46 votes

Correct Option: A

In (B) and (C) when the first letter of input is '$b$' we reach final state, while in the given DFA first letter '$b$' is not a final state. So, (B) and (C) are not accepting same language as the given DFA.

In (D) we can reach final state when the last letter is '$a$', whatever be the previous transitions. But in the given DFA, when the first $2$ letters are '$b$' we can never reach the final state. So, (D) is also accepting a different language than the given DFA.

edited by
29 votes
29 votes

Minimization using set of equivalent states

First set of equivalent states 

$\pi$0 ={ I,II}        I={p,q,r} set of non-final state        II = {s,t} set of final state 

now check states in set I are equivalents or not 

p x a -> s [II , goes to state that is in set II]                q x a -> t [II]                        r x a -> r [I]

p x b -> q [I]                                                           q x b -> r [I]                        r x b -> r[I]

it is clear p,q are equivalent (both states on symbol a goes to states that is in set II , both states on symbol  b goes to states that is in set I) but r behaves differently, set {p,q,r} divides into two set {p,q},{r}

now check states in set II are equivalent or not

s x a -> s[II]                               t x a -> t [II]

s x b -> s[II]                               t x a ->t [II]

so s,t are equivalent states 

that results in 

Second set of equivalent states 

$\pi$1 ={ I,II,III}        I = {p,q}    II =  {r}     III = {s,t} 

check all states in I are equivalents or not  , same for set II and set III using same procedure as above

Third set of equivalent states 

$\pi$2 ={ I,II,III,IV}        I = {p}    II =  {q}     III = {r}        IV = {s,t} 

further 

$\pi$3 =$\pi$2   .i,e that cannot be further minimized 

s and t are equivalent states 

Minimized DFA will be same as given in option A 

0 votes
0 votes

RE corresponding to our DFA is: a(a+b)* + ba(a+b)*

consider option B and C : it will accept string like simple 'b'. Hence, rejected.

Option D: it will accept string like bba which is not a part of our language.Hence, rejected.

So, option A is the right answer.

0 votes
0 votes

b) is incorrect because it accepts string b which is not accepted by the given DFA.

c) is incorrect because it accepts string which is not accepted by the given DFA

d) is incorrect because it accepts string bba which is not accepted by the given DFA.

 

therefore option a 

Answer:

Related questions

65 votes
65 votes
12 answers
4