GATE CSE 2007 | Question: 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$

Comments

we can do this one by Myhill nerode theorem .

First of all remove unreachable states  directly form it

1.unreacable statte are thos which has  no any path from start state .

2. Now  for q1 ->a = Final state

                 q2 - >a  = final state

                q1 ->a = Final state.

               q2 -> b = Final state.

 so q1 and q2 are indistinguisable state  with any string.

so merge them

 

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.

Answer 4

Correct  Option is B.

Answer 5

Hope you have understand