Let $\Sigma = \{0, 1\}$, consider the language $L = \{111\}$, i.e., $L$ contains a single string with three $1$’s. Give an NFA with $4$ states that recognizes $L$...
I am kind of stuck since I can only think of having one with $5$ states, with the last state being a garbage or catch all state that makes sure four or more quantity of $1$'s are not accepted. any intuition would be much appreciated.
To expand Babado's comment, the automaton $$ \rightarrow (1) \xrightarrow{1} (2) \xrightarrow{1} (3) \xrightarrow{1} (4) \rightarrow $$ is indeed an automaton accepting the language $\{111\}$. This automaton is an incomplete deterministic automaton and hence also a non-deterministic automaton. It is actually the minimal incomplete deterministic automaton accepting $\{111\}$. The minimal complete deterministic automaton of $\{111\}$ would be the $5$-state automaton ${\cal A} = (Q, \{0,1\}, \cdot, i, F)$ with $Q = \{0, 1, 2, 3, 4\}$, $i = 1$, $F = \{4\}$ and the transitions given by the following table \begin{array}{c|c|} q & 1 & 2 & 3 &4 & 0\\ \hline q \cdot 0 &0 &0 &0 &0 &0\\ \hline q \cdot 1 &1 &1 &1 &1&0\\ \hline \end{array} Note that $0$ is a sink state of $\cal A$.