The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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$?

asked in Theory of Computation by Veteran (106k points)
edited by | 1.4k views
It is DFA for language containing strings not starting with " bb " .

2 Answers

+29 votes
Best answer

(A) is the answer.

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.

answered by Veteran (363k points)
edited by
@Arjun Suresh Sir is there any more counterexample for option D?

@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)*

+15 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} 


$\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 

answered by Veteran (55.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,601 answers
63,743 users