Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Self-verifying finite automaton
open-in-new
<p>In <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>, a self-verifying finite automaton (SVFA) is a special kind of a <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a> (NFA) with a symmetric kind of nondeterminism introduced by <a href="/facts/Juraj_Hromkovi%25C4%258D/nA3f0xck">Hromkovič</a> and Schnitger. Generally, in self-verifying nondeterminism, each computation path is concluded with any of the three possible answers: <i>yes</i>, <i>no</i>, and <i>I do not know</i>. For each input string, no two paths may give contradictory answers, namely both answers <i>yes</i> and <i>no</i> on the same input are not possible. At least one path must give answer <i>yes</i> or <i>no</i>, and if it is <i>yes</i> then the string is considered accepted. SVFA accept the same class of languages as <a href="/facts/Deterministic_finite_automata/9conRLFS">deterministic finite automata</a> (DFA) and NFA but have different <a href="/facts/State_complexity/dIaeAN82">state complexity</a>. </p>