GATE2007-75

Question

Consider the following Finite State Automaton:

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

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Answer 1

Answer will be 2 state.

Comments

1. q3 is unreachable state, hence it can be removed.
2. States q1 and q2 are indistiguishable, so, they can be merged.

Answer 2

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.

Answer 3

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.

Comments

PLease tell how Q2  and q1 are equal ?

---

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.