Self-verifying finite automaton

<h2 id="formal-definition">Formal definition</h2>
An SVFA is represented formally by a <a href="/facts/N-tuple/BI1HIxL8">6-tuple</a>,
A=(Q, Σ, Δ, q0, Fa, Fr)
such that (Q, Σ, Δ, q0, Fa)
is an <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">NFA</a>,
and Fa, Fr are disjoint subsets of Q.
For each word w = a1a2 … an,
a computation is a sequence of states
r0,r1, …, rn, in Q with the following conditions:

<ol><li>r0 = q0</li>
<li>ri+1 ∈ Δ(ri, ai+1), for i = 0, …, n−1.</li></ol>
If rn ∈ Fa then the computation is accepting,
and if rn ∈ Fr then the computation is rejecting.
There is a requirement that for each w
there is at least one accepting computation
or at least one rejecting computation
but not both.

<h2 id="results">Results</h2>
Each DFA is a SVFA, but not vice versa.
Jirásková and <a href="/facts/Giovanni_Pighizzini/FM8mbRrI">Pighizzini</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
proved that 
for every SVFA of n states,
there exists an equivalent DFA
of 
 
 
 
 g
 (
 n
 )
 =
 Θ
 (
 
 3
 
 n
 
 /
 
 3
 
 
 )
 
 
 {\displaystyle g(n)=\Theta (3^{n/3})}
 
 states.
Furthermore, for each positive integer n, there exists an n-state SVFA
such that the minimal equivalent DFA has exactly 
 
 
 
 g
 (
 n
 )
 
 
 {\displaystyle g(n)}
 
 states.
Other results on the <a href="/facts/State_complexity/dIaeAN82">state complexity</a> of SVFA
were obtained by Jirásková and her colleagues.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hromkovič, Juraj; Schnitger, Georg (2001). "On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata". Information and Computation. 169 (2): 284–296. doi:10.1006/inco.2001.3040. ISSN 0890-5401. <a href="https://doi.org/10.1006%2Finco.2001.3040" target="_blank">https://doi.org/10.1006%2Finco.2001.3040</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata". Information and Computation. 209 (3): 528–535. doi:10.1016/j.ic.2010.11.017. ISSN 0890-5401. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Jirásková, Galina (2016). "Self-Verifying Finite Automata and Descriptional Complexity" (PDF). Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science. Vol. 9777. pp. 29–44. doi:10.1007/978-3-319-41114-9_3. ISBN 978-3-319-41113-2. ISSN 0302-9743. <a href="978-3-319-41113-2" target="_blank">978-3-319-41113-2</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). "Operations on Self-Verifying Finite Automata". Computer Science -- Theory and Applications. Lecture Notes in Computer Science. Vol. 9139. pp. 231–261. doi:10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. ISSN 0302-9743. <a href="978-3-319-20296-9" target="_blank">978-3-319-20296-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Self-verifying finite automaton open-in-new

Self-verifying finite automaton