Consider a nondeterministic finite automaton $M$ over an alphabet $\Sigma$,
where the states can be either accepting, rejecting, or neutral. Let $L_a(M)$ (resp., $L_r(M)$) be the set of strings taking $M$ from the start state to an accepting state (resp., rejecting state). Then $M$ is said to be self-verifying
if $L_a(M) \cup L_r(M) = \Sigma^*$ and $L_a(M) \cap L_r(M) = \emptyset$.
That is, the strings reaching an accepting state and the strings reaching a rejecting state form a disjoint partition of $\Sigma^*$. The language accepted by $M$ is $L_a(M)$.

Using a result of Moon, Moser [On cliques in graphs, Israel J. Math. 3, 23--28, 1965], we get an optimal simulation of self-verifying automata by deterministic finite automata. Then we study the complexity of regular operations on languages represented by self-verifying automata, and get the tight upper bounds for union ($mn$), intersection ($mn$), reversal ($2n+1$), star (${3\over 4}2^n$), left quotient ($2^n-1$), right quotient ($3^{n/3}$), and asymptotically tight upper bound for concatenation ($3^{m/3}2^n$). Next we prove that given a nondeterministic automaton $M$ with accepting, rejecting, and neutral states, it is PSPACE-complete to determine if $M$ is self-verifying. Finally, we study the complexity of the membership, emptiness, universality, and minimization problems for self-verifying automata.