In automata theory, a self-verifying finite automaton (SVFA) is a special kind of a nondeterministic finite automaton (NFA) with a symmetric kind of nondeterminism introduced by Hromkovič and Schnitger.
[1] Generally, in self-verifying nondeterminism, each computation path is concluded with any of the three possible answers: yes, no, and I do not know.
SVFA accept the same class of languages as deterministic finite automata (DFA) and NFA but have different state complexity.
Jirásková and Pighizzini[2] proved that for every SVFA of n states, there exists an equivalent DFA of
Furthermore, for each positive integer n, there exists an n-state SVFA such that the minimal equivalent DFA has exactly