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

Concept: a “minimum state automaton equivalent to a regular expression” question asks for the fewest states needed to correctly accept every string in the language and reject every string outside it. Under this convention an automaton need not be a complete/total DFA (one with a transition defined on every symbol from every state) — an incomplete (partial) automaton, where a missing transition is simply treated as rejection, is valid here, so a dedicated extra trap state is not required unless the automaton must remain total. (An NFA built for the same language, with no trap state either, reaches the same count — but a matching state count between the two is not itself a general proof that they are separately minimal; each still needs its own distinguishability check.)

Building the minimal automaton for a*b(a+b):

1. The pattern matches strings of the form an b x, where n ≥ 0 and x ∈ {a, b} — any number of leading a's, then exactly one b, then exactly one final symbol.

2. State S0 (start): still reading the leading a's; the required b has not been seen yet. Reading 'a' stays in S0; reading 'b' moves to S1.

3. State S1: the required b has just been read, and exactly one final symbol is still needed. Reading either 'a' or 'b' moves to S2.

4. State S2 (accepting): the pattern is complete — stopping the input here is accepted. No transition needs to be defined out of S2 for this state count: any symbol read after S2 simply has no move, and an automaton with an undefined move is treated as rejecting from there, without needing a separate state to do that rejecting.

Why three states are enough (none can be merged):

• S2 is distinguishable from S0 and S1: only from S2 does stopping the input immediately (the empty continuation) lead to acceptance.

• S1 is distinguishable from S0: the continuation 'a' leads to acceptance from S1 (S1 → S2, accept), but the same continuation from S0 leaves the automaton in S0, unaccepted.

• So S0, S1, S2 are pairwise distinguishable and this three-state automaton correctly accepts exactly a*b(a+b) — no fourth state is needed to reach that correctness.

Cross-check: a stricter reading that additionally requires the automaton to be a fully complete/total DFA — one where every state has a defined transition on every symbol, including an explicit trap/dead state purely to keep rejecting any input appended after a completed match — would add a fourth state, giving 4. That is a legitimate alternative formalization, which is why this exact previous-year question has drawn repeated questions from learners. But the standard NTA-sourced reference for this specific UGC NET (June 2019, Computer Science) question, corroborated by other independent PYQ reference sources, reports 3 as the accepted count, following the convention that does not require that extra completeness.