The Gateway to Computer Science Excellence
+18 votes
1.3k views

Consider the following Finite State Automaton:

The minimum state automaton equivalent to the above FSA has the following number of states:

  1. $1$
  2. $2$
  3. $3$
  4. $4$
in Theory of Computation by Veteran (105k points)
edited by | 1.3k views

3 Answers

+25 votes
Best answer

Answer will be 2 state.

by Boss (38.4k points)
edited by
+10
1. q3 is unreachable state, hence it can be removed.
2. States q1 and q2 are indistiguishable, so, they can be merged.
+11 votes
It is B.

The state Q3 is redundant as it is not reachable. And the Regular expression b*a(a+b)* can be made with two states.

Q1-->b-->Q1

Q1-->a-->Q2

Q2-->a-->Q2

Q2-->b-->Q2.

Clearly there are 2 states.
by Boss (19.9k points)
+9 votes

Minimum Finite Automata = DFA - (Unreachable States + Equal States)

                                      = DFA - ( q3 + q2)

Here q2 is equal state with q1 and q3 is unreachable state

So total 2 states left.  

Hence Option B is Ans.

by Boss (23.8k points)
0
PLease tell how Q2  and q1 are equal ?
+4
Partition the sets in 2 parts final and non final states you will note that all transitions of q1 and q2 is in same set like that q1 and q2 is equal.

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
50,647 questions
56,497 answers
195,490 comments
100,818 users