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$

edited | 1.3k views

by Boss (38.4k points)
edited
+10
1. q3 is unreachable state, hence it can be removed.
2. States q1 and q2 are indistiguishable, so, they can be merged.
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)

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.