1.7k views

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 | 1.7k views
0
It is DFA for language containing strings not starting with " bb " .

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
0
@Arjun Suresh Sir is there any more counterexample for option D?
+2

@Sandeep Suri,

on state Q, given FA is going to dead state but in option D it's looping on state Q.

RE for option D = (a + b+a) (a+ b)*

for option A = (a + ba)(a+b)*

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

1
2