Odpowiedź: 16. Zbudowanie automatu nie jest trudne. Wystarczy się zastanowić, co tak naprawdę musimy pamiętać. Mogę podpowiedzieć, że będzie 15 stanów, w których faktycznie “kręci się” automat i jeden stan startowy (stan dla słowa pustego). Pokazanie automatu, to wykazanie, że 16 stanów wystarczy.
By pokazać, że potrzeba 16 stanów wykonujemy podobne rozumowanie, co zadanie wcześniej. Oczywiście nie bierzemy wszystkich trzyliterowych słów. Wybieramy tylko pewien podzbiór. Patrząc na automat powinno to być dość proste.