In a recent IT class we got the task of creating a finite state automaton that accepts only the words "auto" "automarke" "tomaten" and "automaten" and no others. Basically the whole class had no problems finding a 17 state solution, except for the guy two seats next to me who is incredibly convinced that its possible in 14, without justification. The front row failed trying to prove mathematically and logically why you need at least 17 states to do this, and now I am quite interested in the following question:
How would you go about proving the minimum number of states for this specific automaton, or any general automaton?
P.S. I can show my 17 state solution if requested
P.P.S I was redirected here from tcs.se