Wie viele DFAs akzeptieren zwei vorgegebene Zeichenfolgen?

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$$\Sigma=\{0,1\}$$DFA(n)$$n$$|DFA(n)| = n^{2n}2^n$

Betrachten Sie nun zwei Zeichenfolgen und definieren Sie als die Anzahl der Elemente von , die sowohl als auch akzeptieren .$x,y\in\Sigma^*$$K(x,y)$$DFA(n)$ $x$$y$

Frage: Wie komplex ist die Berechnung von ?$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 $n\ge1$$DFA(n)$$n^{2n}2^n$$x,y\in\{0,1\}^*$$K_n(x,y)$$DFA(n)$ x y K n ( x , y ) p o l y ( n , | x | , | y |$x$$y$$K_n(x,y)$$poly(n,|x|,|y|)$

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).$n$$x$$y$

Zuallererst, wenn Sie daran interessiert sind,$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)$$x$$y$$p$

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 + $p \ge 1/n$$x$$y$$x$$y=00$( n - 1 ) n .$p= \frac{n+1}{(n-1)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?$x$$y$$n$$n!$$p=1$

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:$n$$K$

Bei der Eingabe x , y , wo x , y ∈ & Sigma; $x$$y$$x,y\in\Sigma^*$

1. speichere x und $x$$y$
2. Zähler c auf 0 initialisieren$c$$0$
3. für jeden Ihrer n 2 n 2 n DFAs$n^{2n} 2^n$

4. ein. simuliere es für beide Wörter (dieser Schritt ist O ( | x y | ) )$\mathcal{O}(|xy|)$

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

5. Ausgabe $c$

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