Übergangsmonoid-Mitgliedschaft für DFAs

9

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 verallgemeinernA=(Q,Γ,δ,F)faaΓfa:QQfa(q)=δ(q,a)w=a1,,am wo Funktion Zusammensetzung bezeichnet. Weiterhin bezeichnen wir G = { f w | w & egr ; & Ggr; * } und G Monoid ist.fw=fa1famG={fwwΓ}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:QQfGwf=fww

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

maomao
quelle

Antworten:

9

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 ag . 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 seinf:QQghaΓh=faggGgfϵQaber.

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 Γ = { 0p1,,pkk(i,x)i{1,,k}xi{0,1,,pi1}Γ={0}und die Übergangsfunktion . Die Funktion f 0 : Q Q.δ((i,x),0=(i,x+1modpi)f0:QQ ist gegeben durch

f0(i,x)=(i,x+1modpi).

Betrachten Sie nun die Funktion g:QQ gegeben durch

g(i,x)=(i,x1modpi).

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ß ing=f0nn=p1×p2××pk10n|Q|=p1++pkn.Q

gG

DW
quelle