Number of states of a finite automaton recognizing all words beginning with some fixed string $x$

248 Views Asked by At

For a string $x \in \{a,b\}^\ast$ with $|x| = n$, how many states are required for an FA accepting the language of all strings in $\{a,b\}$ that begin with $x$? For each of these states, describe the strings that cause the FA to be in that state.


So $x$ looks like any combination of $a$'s and $b$'s right? Is the answer two because $x$ could begin with $a$ or $b$, and those are both accepted in the language of all strings in $\{a,b\}$?