27 votes 27 votes Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states: $1$ $2$ $3$ $4$ Theory of Computation normal gatecse-2007 theory-of-computation finite-automata minimal-state-automata + – go_editor asked Apr 23, 2016 • edited Jun 28, 2019 by Pooja Khatri go_editor 8.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 35 votes 35 votes Answer will be 2 state. ManojK answered Apr 23, 2016 • edited Jun 4, 2021 by S k Rawani ManojK comment Share Follow See 1 comment See all 1 1 comment reply Manu Thakur commented Nov 28, 2017 reply Follow Share 1. q3 is unreachable state, hence it can be removed. 2. States q1 and q2 are indistiguishable, so, they can be merged. 24 votes 24 votes Please log in or register to add a comment.
11 votes 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. Gate Keeda answered Apr 29, 2016 Gate Keeda comment Share Follow See all 0 reply Please log in or register to add a comment.
9 votes 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. Rajesh Pradhan answered Dec 11, 2016 Rajesh Pradhan comment Share Follow See all 2 Comments See all 2 2 Comments reply Dulqar commented Jan 9, 2017 reply Follow Share PLease tell how Q2 and q1 are equal ? 0 votes 0 votes Yash4444 commented Jul 15, 2017 reply Follow Share 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. 6 votes 6 votes Please log in or register to add a comment.
