How many states are there in a minimum state automata equivalent to regular…

Answer: 4 states.

Explanation: The regular expression a* b (a + b) describes strings that have any number (possibly zero) of leading a's, followed by a single b, and then exactly one final symbol which can be a or b. Valid strings have the form a^n b x with n >= 0 and x in {a, b}. No symbols are allowed after that final symbol.

• q0 (start): represents the prefix of only a's seen so far. On input 'a' stay in q0. On input 'b' go to q1.

• q1 (after b, waiting for final symbol): non-accepting. On input 'a' or 'b' go to q2 (the accepting state).

• q2 (accepting): indicates we have seen a^n b x (the required pattern) and would accept if input ends now. On any further input ('a' or 'b') transition to q3 (trap).

• q3 (trap, non-accepting): once extra symbols appear after the required final symbol, the string cannot be in the language. On 'a' or 'b' remain in q3.

Why these states are all necessary (minimality):

• q2 is distinguishable from others because the empty suffix (i.e., ending the input immediately) is accepted from q2 but not from q0, q1, or q3.

• q1 is distinguishable from q0: from q1 the suffix "a" leads to acceptance (q1 -> q2 -> accept), whereas from q0 the same suffix leaves you in q0 (not accepted).

• q3 (trap) is distinguishable from q0 (and others) by a suffix such as "ba": from q0 the suffix "ba" leads to acceptance (q0 -> q1 -> q2 -> accept), but from q3 any suffix keeps you in the trap and is not accepted.

Since all four states are pairwise distinguishable, they cannot be merged, so the minimal DFA requires 4 states.