  The automation of decision procedures makes certification essential. We
suggest to use determinacy of turn-based two-player games with regular winning
conditions in order to generate certificates for the number of states that a
deterministic finite automaton (DFA) needs in order to recognize a given
language. Given a language $L$ and a bound $k$, recognizability of $L$ by a DFA
with $k$ states is reduced to a game between Prover and Refuter. The
interaction along the game then serves as a certificate. Certificates generated
by Prover are minimal DFAs. Certificates generated by Refuter are faulty
attempts to define the required DFA. We compare the length of offline
certificates, which are generated with no interaction between Prover and
Refuter, and online certificates, which are based on such an interaction, and
are thus shorter. We show that our approach is useful also for certification of
separability of regular languages by a DFA of a given size. Unlike DFA
minimization, which can be solved in polynomial time, separation is
NP-complete, and thus the certification approach is essential. In addition, we
prove NP-completeness of a strict version of separation.
