when the automaton accepts a unary language. The non-emptiness problem (is the language of an input AFA non-empty?), the universality problem (is the complement of the language of an input AFA empty?), and the equivalence problem (do two input AFAs recognize the same language) are PSPACE-complete for AFAs. References Finite automata