The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.2k 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 (99.6k points)
edited by | 1.2k views

3 Answers

+23 votes
Best answer

Answer will be 2 state.

by Boss (38.3k 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.
+10 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)
+8 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.5k 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.
Answer:

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
49,984 questions
55,135 answers
190,487 comments
85,107 users