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 se concluye con cualquiera de las tres respuestas posibles: sí , no y no lo sé . Para cada cadena de entrada, no hay dos rutas que puedan dar respuestas contradictorias, es decir, ambas respuestas sí y no en la misma entrada no son posibles. Al menos una ruta debe dar respuesta sí ono , y si es sí , la cadena se considera aceptada. SVFA acepta la misma clase de lenguajes que los autómatas finitos deterministas (DFA) y NFA, pero tienen una complejidad de estado diferente .
Definicion formal
Un AFVS está representado formalmente por una tupla de 6 , A = ( Q , Σ, Δ, q 0 , F a , F r ) tal que ( Q , Σ, Δ, q 0 , F a ) es un NFA , y F un , F r son subconjuntos disjuntos de Q . Para cada palabra w = a 1 a 2 … a n , un cálculo es una secuencia de estados r 0 , r 1 ,…, r n , en Q con las siguientes condiciones:
- r 0 = q 0
- r i + 1 ∈ Δ ( r i , a i + 1 ), para i = 0,…, n − 1 .
Si r n ∈ F a entonces el cálculo está aceptando, y si r n ∈ F r entonces el cálculo está rechazando. Existe el requisito de que para cada w haya al menos un cálculo de aceptación o al menos un cálculo de rechazo, pero no ambos.
Resultados
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 deestados. Además, para cada entero positivo n , existe un SVFA de estado n tal que el DFA equivalente mínimo tiene exactamente estados.
Jirásková y sus colegas obtuvieron otros resultados sobre la complejidad estatal de SVFA. [3] [4]
Referencias
- ^ Hromkovič, Juraj; Schnitger, Georg (2001). "Sobre el poder de Las Vegas para la complejidad de la comunicación unidireccional, OBDD y autómatas finitos" . Información y Computación . 169 (2): 284-296. doi : 10.1006 / inco.2001.3040 . ISSN 0890-5401 .
- ^ Jirásková, Galina; Pighizzini, Giovanni (2011). "Simulación óptima de autómatas autoverificables mediante autómatas deterministas" . Información y Computación . 209 (3): 528–535. doi : 10.1016 / j.ic.2010.11.017 . ISSN 0890-5401 .
- ^ Jirásková, Galina (2016). "Autómatas finitos de autoverificación y complejidad descriptiva" (PDF) . Complejidad descriptiva de los sistemas formales . Apuntes de conferencias en informática. 9777 . págs. 29–44. doi : 10.1007 / 978-3-319-41114-9_3 . ISBN 978-3-319-41113-2. ISSN 0302-9743 .
- ^ Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). "Operaciones en autómatas finitos autoverificantes". Ciencias de la Computación - Teoría y Aplicaciones . Apuntes de conferencias en informática. 9139 . págs. 231-261. doi : 10.1007 / 978-3-319-20297-6_16 . ISBN 978-3-319-20296-9. ISSN 0302-9743 .