Übergangsmonoid-Mitgliedschaft für DFAs

Bei einer vollständigen DFA , können wir eine Sammlung von Funktionen definieren , f eine für jedes a ∈ Γ und mit f ein : Q → Q , f einen ( q ) = δ ( q , a ) . Wir können diesen Begriff auf ein Wort w = a 1 , ⋯ , a m und f w verallgemeinern$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$ wo ∘ Funktion Zusammensetzung bezeichnet. Weiterhin bezeichnen wir G = { f w | w & egr ; & Ggr; * } und G Monoid ist.$f_w=f_{a_1}\circ \cdots \circ f_{a_m}$$\circ$$G=\{f_w\mid w\in \Gamma^*\}$$G$

[ wird im Standardlehrbuch normalerweise als Übergangsmonoid bezeichnet , aber hier reproduziere ich die Definition aus Gründen der Klarheit.]$G$

Die Frage ist, ob wir bei gegebener Funktion f ∈ G (idealerweise in Polynomzeit) entscheiden können, und wenn dies der Fall ist (dh es gibt ein w, so dass f = f w ist ), ob w ist nur polynomiell lang oder kann exponentiell lang sein? $f:Q\rightarrow Q$$f\in G$$w$$f=f_w$$w$

[Ich denke, dass ein solches Wort tatsächlich exponentiell lang sein könnte, aber ich suche nach einem einfachen Beispiel.]

Entscheidbarkeit

Es ist entscheidbar. Es gibt nur endlich viele mögliche Funktionen , so können Sie dies als Graph Erreichbarkeitsproblem modellieren kann, mit einem Scheitelpunkt pro Funktion und einer Kante g → h , wenn es existiert ein & egr ; & Ggr; so dass h = f a ∘ g . Das Testen, ob eine Funktion g in G ist, reduziert sich dann auf das Testen, ob g im Graphen von f ϵ aus erreichbar ist . Sie können das kürzeste derartige Wort finden, indem Sie das erste Mal die Breite verwenden. Die Laufzeit kann in Q exponentiell sein$f:Q \to Q$$g \to h$$a \in \Gamma$$h = f_a \circ g$$g$$G$$g$$f_\epsilon$$Q$aber.

Länge des Wortes

Das kürzeste Wort dieser Art könnte exponentiell lang sein. Hier ist ein Beispiel für einen solchen DFA. Sei die ersten k Primzahlen. Dann hat ein Zustand die Form ( i , x ), in der i ∈ { 1 , … , k } und x i ∈ { 0 , 1 , … , p i - 1 } sind . Definieren Sie einen DFA mit einem unären Alphabet Γ = { $p_1,\dots,p_k$$k$$(i,x)$$i \in \{1,\dots,k\}$$x_i \in \{0,1,\dots,p_i-1\}$$\Gamma=\{0\}$und die Übergangsfunktion . Die Funktion f 0 : Q → $\delta((i,x),0 = (i,x+1 \bmod p_i)$$f_0 :Q \to Q$ ist gegeben durch

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

Betrachten Sie nun die Funktion $g:Q \to Q$ gegeben durch

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

Es ist möglich, den chinesischen Restsatz zu verwenden, um zu zeigen, dass wobei n = p 1 × p 2 × ⋯ × p k - 1 , und dass 0 n das kürzeste derartige Wort ist. Darüber hinaus | Q | = p 1 + ⋯ + p k , also ist n exponentiell groß in$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$

$g$$G$