Consider the language \(L\) given by the regular expression \((a+b)^{*} b…

Answer: 4 states.

Reasoning: The language consists of all strings of length at least 2 whose penultimate (second-last) symbol is b. To decide acceptance after reading the whole input we only need to know information about the last one or two symbols seen while scanning left to right, so a finite-state machine with a small number of states suffices.

Construct a minimal DFA with four states that track the necessary cases:

• State S0 (start, also represents any string whose last symbol is not b, including the empty string). This is a non-accepting state.

• State S1 (last symbol is b, but penultimate symbol is not b or does not exist). This is a non-accepting state.

• State S2 (penultimate symbol is b and last symbol is a). This is an accepting state.

• State S3 (penultimate symbol is b and last symbol is b). This is an accepting state.

Transitions (on reading the next symbol, update last and penultimate accordingly):

• From S0: on a -> S0 (last becomes a, penultimate is not b); on b -> S1 (last becomes b, penultimate not b or nonexistent).

• From S1: on a -> S2 (penultimate becomes b, last becomes a, so accept); on b -> S3 (penultimate becomes b, last becomes b, so accept).

• From S2: on a -> S0 (penultimate becomes a, last becomes a); on b -> S1 (penultimate becomes a, last becomes b).

• From S3: on a -> S2 (penultimate becomes b, last becomes a); on b -> S3 (penultimate becomes b, last becomes b).

Accepting states: S2 and S3 (because their penultimate symbol is b).

Minimality proof (Myhill–Nerode): exhibit four pairwise distinguishable prefixes.

1. Take the prefixes: the empty string ε (in S0), the string b (in S1), the string ba (in S2), and the string bb (in S3).

2. Show they are pairwise distinguishable by simple continuations:

   • ε vs b: append a. εa = a is not in the language, but ba is in the language, so ε and b are distinguishable.

   • b vs ba: append the empty string. b is not in the language (length 1), ba is in the language, so b and ba are distinguishable.

   • ba vs bb: append a. baa is not in the language (penultimate is a), but bba is in the language (penultimate is b), so ba and bb are distinguishable.

Since we have four pairwise distinguishable equivalence classes, any minimal DFA requires at least four states. The constructed DFA uses exactly four states, so it is minimal.