¿Los autómatas XOR (NXA) para lenguajes finitos se benefician de los ciclos?

Un autómata Xor no determinista (NXA) es sintácticamente un NFA, pero se dice que NXA acepta una palabra si tiene un número impar de rutas de aceptación (en lugar de al menos una ruta de aceptación en el caso de NFA).

Es fácil ver que para un lenguaje regular finito , existe un NFA mínimo que no contiene ningún ciclo (si un ciclo era accesible desde el estado inicial y se llega a un estado de aceptación, su idioma no es finito).$L$

Este no es necesariamente el caso de los NXA.

Denote por la complejidad del estado xor de un lenguaje L ,$xsc(L)$$L$

y por la complejidad del estado xor acíclico de L (es decir, el tamaño de un NXA acíclico más pequeño que acepta L ).$axsc(L)$$L$$L$

¿Es cierto que para cada lenguaje finito : a x s c ( L ) = x s c ( L ) $L$

$$axsc(L)=xsc(L)\ ?$$

Creo que la respuesta es afirmativa. Quizás haya una prueba más simple, pero aquí hay un bosquejo de una prueba que usa álgebra lineal.

Al igual que domotorp, veremos una configuración de un autómata XOR de estado n como un vector en V = GF (2) ⁿ .

Deje que L sea ​​un lenguaje finito sobre un alfabeto Σ = {1, ..., k }, y considere un autómata XOR para L con el número mínimo de estados. Sea n el número de estados. Suponemos que los estados están etiquetados como 1, ..., ny el estado 1 es el estado inicial.

Primero configuramos la notación. Supongamos que v ₀ = (1, 0,…, 0) ^T ∈ V es el vector elemental correspondiente al estado inicial, y s es el vector de fila cuya i ésima entrada es 1 si y solo si el estado i es un estado de aceptación. El subespacio R = { v : s v = 0} de V corresponde a los vectores de configuración que se rechazan.

Para cada a ∈Σ, sea A _a la matriz n × n sobre GF (2) que representa la transición causada por la letra a . Por ejemplo, el vector de configuración después de leer la cadena de entrada a b es A _b A _a v ₀ . Para una cadena σ = a ₁ ... a _t , denotamos el producto A _{a t} ... A _{a 1} por M ( σ ). Deje S = { A ₁, ..., A _k }.

Un subespacio W de V se dice que es S - invariante cuando A W ⊆ W por cada A ∈ S . En nuestro contexto, esto significa que una vez que el vector de configuración entra en W , no hay forma de salir de W leyendo más letras.

Debido a que este autómata XOR tiene el número mínimo de estados, tenemos las siguientes propiedades.

• El único subespacio S- invariante de V que contiene v ₀ es V en sí. Esto se debe a que si W es un subespacio invariante S adecuado que contiene v ₀ , entonces podemos usar W en lugar de V , contradiciendo la minimidad.
• El único subespacio invariante S contenido en R es {0}. Esto se debe a que si W es un subespacio invariante S no trivial contenido en R , entonces podemos usar el espacio vectorial cociente V / W en lugar de V , contradiciendo nuevamente la minimidad.

Debido a que L es finito, dejar que m sea un número entero mayor que la longitud de cualquier cadena en L .

Lema 1 . Para cualquier cadena σ de longitud al menos m , tenemos que M ( σ ) = 0.

Prueba. Primero demostramos que para cualquier cadena σ de longitud al menos m , tenemos que M ( σ ) v ₀ = 0. Sea W el subespacio de V atravesado por { M ( σ ) v ₀ : σ es una cadena de longitud al menos m }. Por definición, W es S- invariante. Debido a que el autómata XOR en cuestión rechaza estas cadenas sigma , W está contenido en R . Por lo tanto W = {0}, lo que significa queM ( σ ) v ₀ = 0 para todas esas cadenas σ .

Consideremos ahora cualquier vector v ∈ V . Debido a que el único subespacio S- invariante de V que contiene v ₀ es V en sí, v puede escribirse como una combinación lineal de vectores de la forma M ( τ ) v ₀ para algunas cadenas τ . Porque M ( σ ) M ( τ ) v ₀ = M ( τ σ ) v ₀= 0 (la última igualdad se deduce del párrafo anterior porque la longitud de τ σ es al menos m ), sostiene que M ( σ ) v = 0. ■

Necesitamos un hecho más del álgebra lineal.

Lema 2 . Supongamos que A ₁ ,…, A _k sean n × n matrices sobre un campo, y defina M ( σ ) como anteriormente. Si hay m ≥ 0 tal que M ( σ ) = 0 para cada cadena σ de longitud al menos m , entonces las matrices A ₁ , ..., A _k son simultáneamente similares a las matrices triangulares estrictamente inferiores (es decir, existe una n × n matriz no singular P tal que las matrices P ⁻¹ A₁ P , ..., P ⁻¹ A _k P son estrictamente inferiores triangulares).

El caso de k = 1 es una caracterización bien conocida de matrices nilpotentes, y Lemma 2 se puede probar de la misma manera.

Ahora considere el autómata XOR de estado n en el que la matriz de transición correspondiente al símbolo a ∈Σ está dada por P ⁻¹ A _a P , el vector de configuración inicial está dado por P ⁻¹ v ₀ y el vector característico (fila) de los estados de aceptación está dada por s P . Por construcción, este autómata XOR acepta el mismo lenguaje L. Debido a que las matrices de transición son estrictamente triangulares más bajas, cada borde de transición en este autómata XOR pasa de un estado con un índice más pequeño a un estado con un índice más grande, y por lo tanto este autómata XOR es acíclico. Aunque el vector de configuración inicial puede tener más de un 1, es fácil convertir este autómata XOR en un autómata XOR habitual con un solo estado inicial para el mismo idioma sin aumentar el número de estados ni arruinar la aciclicidad.

Creo que puedo demostrar que los ciclos no ayudan sobre el alfabeto unario.

$M$$F_2$$v_n$$F_2$$\mod 2$$n$$v_n=M^nv_0$$v_0=(1,0,..,0)$$t$$s\cdot v=0$$s$$M^n$$s\cdot v_n=0$