Autómata finito autoverificable

En la teoría de autómatas , un autómata finito autoverificable ( SVFA ) es un tipo especial de autómata finito no determinista (NFA) con un tipo simétrico de no determinismo introducido por Hromkovič y Schnitger. ^{[ 1 ]} Generalmente, en el no determinismo autoverificable, cada ruta de cálculo concluye con cualquiera de las tres posibles respuestas: sí , no y no lo sé . Para cada cadena de entrada, no puede haber dos rutas que den respuestas contradictorias, es decir, no es posible que ambas respuestas, sí y no, para la misma entrada. Al menos una ruta debe dar la respuesta sí o no , y si es sí, entonces la cadena se considera aceptada. Los SVFA aceptan la misma clase de lenguajes que los autómatas finitos deterministas (DFA) y los NFA, pero tienen diferente complejidad de estado .

Un SVFA se representa formalmente mediante una 6-tupla , A = ( Q _, Σ _, Δ, q0 , Fa , _{Fr )} tal que ( Q , Σ, Δ, q0, Fa) es un NFA, y Fa, Fr _son subconjuntos disjuntos de Q. Para cada palabra w = _a1 , a2 , ... _, an _, una _{computación es} una secuencia de estados r0 _, r1 _, ..., rn _, en Q con las siguientes condiciones:

1. r ₀ = q ₀
2. r _i+1 ∈ Δ( r _i , a _i+1 ), para i = 0, …, n−1 .

Si r _n ∈ F _a, entonces el cálculo es de aceptación, y si r _n ∈ F _r, entonces el cálculo es de rechazo. Se requiere que para cada w exista al menos un cálculo de aceptación o al menos un cálculo de rechazo, pero no ambos.

Cada DFA es un SVFA, pero no al revés. Jirásková y Pighizzini ^{[ 2 ]} demostraron que para cada SVFA de n estados, existe un DFA equivalente de${\displaystyle g(n)=\Theta (3^{n/3})}$estados. Además, para cada entero positivo n , existe un SVFA de n estados tal que el DFA equivalente mínimo tiene exactamente${\displaystyle g(n)}$estados.

Otros resultados sobre la complejidad del estado de SVFA fueron obtenidos por Jirásková y sus colegas. ^{[ 3 ] [ 4 ]}