Wie viele DFAs akzeptieren zwei vorgegebene Zeichenfolgen?

28

Fixiere eine ganze Zahl und ein Alphabet . Definieren Sie als Sammlung aller Automaten mit endlichen Zuständen zu Zuständen mit Startzustand 1. Wir betrachten alle DFAs (nicht nur verbundene, minimale oder nicht entartete). somit ist .n nΣ = { 0 , 1 } Σ={0,1}D F A ( n ) DFA(n)nn| D F A ( n ) | = n 2 n 2 n|DFA(n)|=n2n2n

Betrachten Sie nun zwei Zeichenfolgen und definieren Sie als die Anzahl der Elemente von , die sowohl als auch akzeptieren .x , y Σ x,yΣ K ( x , y ) K(x,y)D F A ( n )DFA(n) x xyy

Frage: Wie komplex ist die Berechnung von ?K ( x , y )K(x,y)

Diese Frage hat Auswirkungen auf das maschinelle Lernen .

Edit: Jetzt, da es eine Fülle von Fragen gibt, ist wohl etwas mehr Präzision in der Formulierung angebracht. Für sei die Sammlung von Automaten, wie oben definiert. Definieren Sie für als die Anzahl der Automaten in , die sowohl als auch akzeptieren . Frage: Kann in der Zeit berechnet werden ?n 1 D F A ( n ) n 2 n 2 n x , y { 0 , 1 } * K n ( x , y ) D F A ( n )n1DFA(n)n2n2nx,y{0,1}Kn(x,y)DFA(n) x y K n ( x , y ) p o l y ( n , | x | , | y | )xyKn(x,y)poly(n,|x|,|y|)

Aryeh
quelle
2
Wenn Sie einen DFA reparieren, ohne die Endzustände zu reparieren, ordnet er x und y demselben Zustand zu. In diesem Fall besteht die einzige Einschränkung darin, dass der Zustand endgültig sein muss, oder er ordnet sie in zwei verschiedenen Zuständen zu Die einzige Einschränkung ist, dass beide endgültig sein müssen. Daher würde ich Ihr Problem umformulieren als "Wie viele DFAs ordnen x und y verschiedenen Zuständen zu?".
a3nm
3
Aryeh, kannst du die Anzahl erklären ? Ich kann den Faktor verstehen. Hinzugefügt: Hoppla, ich habe vergessen, die Endzustände anzugeben. Wie auch immer, um der anderen willen, hier ist die Zählung. Geben Sie für jeden Status an, wohin die Eingänge und . das macht . Geben Sie die Menge der Endzustände an. das ist . n2n2nn2n2n2n2n0011n2nn2n2n2n
Srivatsan Narayanan
2
In der Tat ist es mir egal, was mit anderen Zeichenfolgen als und passiert . Ich denke, man braucht eine bestimmte Anzahl von Punkten, um ein Kopfgeld zu starten? xxyy
Aryeh
4
Der kleinste Automat, der und akzeptiert, hat einen einzelnen Zustand, daher halte ich es nicht für schrecklich informativ ...xxyy
Aryeh
3
Hier ist eine Idee: Wir müssen nur die Anzahl der DFAs mit n Zuständen kennen, die auf x und y im gleichen Zustand enden . Diese Zahl sei m und M sei die Gesamtzahl der DFAs, dh M = n 2 n 2 n . Dann lautet die Antwort 1nxymMM=n2n2n2 m+112m+14(Mm)mxyx=0ab=1blmax{a,b}max{a,b}0a0a1b1bmm

Antworten:

1

Die Frage ist also ziemlich kurz, aber sehr interessant. Ich nehme an, dass die Eingabe in Unary und und in Binary ist (oder wir haben Probleme, wie durch Kai's Antwort hervorgehoben).nnxxyy

Zuallererst, wenn Sie daran interessiert sind,K(x,y)K(x,y) näherungsweise kennen möchten, können Sie zunächst nur ein paar zufällige DFAs generieren, die Ihnen (whp) eine gute Annäherung geben. (Ich frage mich, ob diese Komplexitätsklasse einen Namen hat.)

Dann scheint es ein schwieriges Problem zu sein , K ( x , y ) genau zu kennen. Wie in den Kommentaren von a3_nm und Kaveh ausgeführt, entspricht die Frage der Bestimmung der Anzahl der Automaten, für die x und y den gleichen Zustand annehmen . Ich werde die Wahrscheinlichkeit, dass sie in den gleichen Zustand übergehen, mit p bezeichnen .K(x,y)xyp

Update: Einige der Dinge, die ich hier geschrieben habe, stimmten nicht, jetzt habe ich sie behoben.

Es ist leicht zu erkennen, dass p 1 / n ist . Wir haben Gleichheit, wenn x alle Nullen und y alle Nullen sind, mit Ausnahme des letzten Bits, das eine 1 ist. Gibt es andere Fälle? Ich weiß es nicht. Wenn zum Beispiel x die leere Zeichenkette ist und y = 00 , dann ist p = n + 1p1/nxyxy=00( n - 1 ) n .p=n+1(n1)n

Um das Problem zu vereinfachen, habe ich sogar darüber nachgedacht, was passiert, wenn x und y unär sind. Wenn beide mindestens n sind und ihre Differenz durch n teilbar ist ! , dann ist p = 1 . Gibt es eine einfache Formel für die unäre Version?xynn!p=1

domotorp
quelle
Ich habe das Problem zu klären - ein p o l y ( n , | x | , | y | ) Algorithmus gewünscht wird (oder eine Reduktion von irgendeinem bekannten Hart Problem). Die Stichprobenannäherung wird in dem Artikel verwendet, in dem dieser Kernel vorgestellt wird: portal.acm.org/citation.cfm?id=1577108poly(n,|x|,|y|)
Aryeh
2
Was die unäre Version betrifft : Es gibt nur polynomiell viele unäre Automaten mit n Zuständen, daher würde ich wetten, dass es für diesen Fall einen Polyzeitalgorithmus zur Berechnung von K n ( x , y ) gibt. nKn(x,y)
Aryeh
In der Tat sind Sie absolut richtig, dass die unäre Version berechenbar ist. Ich frage mich immer noch, wie einfach die Formel für ein gegebenes x und y ist.
Domotorp
Die von Ihnen verwendete Reduktion ist fehlerhaft: x und y werden möglicherweise von denselben Automaten akzeptiert und enden in völlig unterschiedlichen Zuständen. Tatsächlich teilen sie möglicherweise nur den Anfangszustand in ihren Pfaden, was für alle Zeichenfolgen gilt.
amnn
@amnn: Es ist drei Jahre her, seit ich das geschrieben habe, aber erklärt der dritte Absatz meiner Antwort nicht, warum ich mich nur mit dem Beenden im selben Zustand befasse?
Domotorp
0

Möglicherweise fehlt mir der Punkt, aber Sie haben angegeben, dass n fest ist, sodass alle DFAs dieser Größe als vorberechnet betrachtet und in einem leicht simulierbaren Format gespeichert werden können. Berechnen Sie K wie folgt:nK

Bei der Eingabe x , y , wo x , y & Sigma; *xyx,yΣ

  1. speichere x und yxy
  2. Zähler c auf 0 initialisierenc
  3. für jeden Ihrer n 2 n 2 n DFAs
  4. ein. simuliere es für beide Wörter (dieser Schritt ist O ( | x y | ) )

    b. Inkrementieren Sie c, wenn beide Simulationsläufe akzeptiert werden

  5. Ausgabe c

Insgesamt ist die Berechnung linear komplex. Die Antwort ist für K ( n , x , y ) ganz anders .

Kai
quelle
3
Es ist klar, dass alle Maschinen funktionieren werden. Aryeh möchte wissen, ob es vielleicht einen polynomialen Zeitalgorithmus oder ein anderes Ergebnis von Härte gibt.
Lev Reyzin
Genau genommen ist dies die Polynomzeit in der Eingabe, wenn n nicht Teil der Eingabe ist, ist es das, was Kai sagte. Aber die Frage ist eindeutig anders.
Domotorp
4
Oh ich verstehe. Ich glaube nicht, dass er das mit "Fix n " meint . Ich denke, die natürliche Interpretation des Problems ist eine, die es nicht trivialisiert.
Lev Reyzin
1
Okay, danke, dass du auf die Lücke hingewiesen hast, Kai. Es wurde behoben :)
Aryeh