1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Use Myhill-Nerode theory (assuming you're interested in deterministic automata). $\endgroup$ – Yuval Filmus Apr 6 '17 at 10:53
  • 1
    $\begingroup$ Check that your 17-state solution is a minimum automaton: that is, (1) every state is reachable, and (2) any two distinct states can be distinguished by a string that leads from one of them to an accepting state, and from the other to a non-accepting state. $\endgroup$ – Emil Jeřábek supports Monica Apr 6 '17 at 11:53
  • $\begingroup$ My first guess would be that his automaton accepts "tomarke". A minimization algorithm for DFAs is presented in these lecture notes by Luca Trevisan. I've informally convinced myself that the obvious 17-state automaton is minimal. $\endgroup$ – David Richerby Apr 6 '17 at 12:09
  • $\begingroup$ @DavidRicherby correct, tomarke is accepted by his automaton $\endgroup$ – 7H3_H4CK3R Apr 6 '17 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.