Membresía de transición monoide para DFA

Dado un DFA completo , podemos definir una colección de funciones para cada y con , . Podemos generalizar esta noción a una palabra y donde denota la composición de la función. Además, denotamos y es monoide.f a a ∈ Γ f a : Q → Q f a ( q ) = δ ( q , a ) w = a 1 , ⋯ , a m f w = f a 1 ∘ ⋯ ∘ f a m ∘ G = { f $A=(Q, \Gamma, \delta, F)$$f_a$$a\in \Gamma$$f_a:Q\rightarrow Q$$f_a(q)=\delta(q, a)$$w=a_1, \cdots, a_m$$f_w=f_{a_1}\circ \cdots \circ f_{a_m}$$\circ$$G=\{f_w\mid w\in \Gamma^*\}$$G$

[ generalmente se llama monoide de transición en el libro de texto estándar, pero aquí reproduzco la definición para mayor claridad.]$G$

La pregunta es, dada una función , ¿podemos decidir (idealmente en tiempo polinómico), y si este es el caso (es decir, existe un tal que ), si es solo polinomialmente largo o puede ser exponencialmente largo? $f:Q\rightarrow Q$$f\in G$$w$$f=f_w$$w$

[Supongo que esa palabra podría ser exponencialmente larga, pero estoy buscando un ejemplo simple.]

Decidability

Es decidible. Solo hay muchas funciones posibles , por lo que puede modelar esto como un problema de accesibilidad gráfica, con un vértice por función y un borde si existe tal que . Luego, probar si una función está en reduce a probar si es accesible en el gráfico desde . Puede encontrar la palabra más corta usando la amplitud por primera vez. Sin embargo, el tiempo de ejecución puede ser exponencial eng → h a ∈ Γ h = f a ∘ g g G g f ϵ$f:Q \to Q$$g \to h$$a \in \Gamma$$h = f_a \circ g$$g$$G$$g$$f_\epsilon$$Q$

Longitud de la palabra

La palabra más corta puede ser exponencialmente larga. Aquí hay un ejemplo de tal DFA. Deje que sean los primeros primos. Entonces, un estado será de la forma donde y . Definir un DFA con el alfabeto unario y la función de transición La función. viene dada por$p_1,\dots,p_k$$k$$(i,x)$$i \in \{1,\dots,k\}$$x_i \in \{0,1,\dots,p_i-1\}$$\Gamma=\{0\}$$\delta((i,x),0 = (i,x+1 \bmod p_i)$$f_0 :Q \to Q$

$$f_0(i,x) = (i,x+1 \bmod p_i).$$

Ahora considere la función dada por$g:Q \to Q$

$$g(i,x) = (i,x-1 \bmod p_i).$$

Es posible utilizar el teorema del resto chino para mostrar que donde , y que es la palabra más corta. Por otra parte, , por lo que es exponencialmente grande en .$g = f_{0^n}$$n=p_1 \times p_2 \times \cdots \times p_k -1$$0^n$$|Q|= p_1 + \dots + p_k$$n$$Q$

En consecuencia, no hay esperanza de un algoritmo de tiempo polinómico que genere una palabra de este tipo. Este hojas todavía abierta la posibilidad de un algoritmo de tiempo polinómico para decidir si es en , sin embargo.$g$$G$