Wörter mit zufälligen DFAs trennen

Eines der interessanten offenen Probleme mit DFAs, die in aufgeführt sind. Gibt es noch offene Probleme mit DFAs? ist die Größe eines DFA, die zum Trennen von zwei Zeichenfolgen der Länge erforderlich ist . Ich bin neugierig, ob es irgendwelche Ergebnisse über die Fähigkeit eines zufälligen DFA gibt, zwei gegebene (nicht zufällige) Zeichenfolgen zu trennen.$n$

Offensichtlich trennt ein zufälliger DFA mit ausreichend vielen Zuständen Zeichenfolgen mit hoher Wahrscheinlichkeit. Insbesondere wenn , ist es unwahrscheinlich , dass ein zufälliger DFA mit O ( n ) -Zuständen jemals denselben Zustand erneut besucht, sobald er den ersten Ort erreicht, an dem u und v unterschiedlich sind, und trennt daher u und v .$u,v \in \Sigma^n$$O(n)$$u$$v$$u$$v$

Können wir es besser machen? Im Idealfall, was die kleinsten st , dass ein zufälliges DFA mit f ( n ) Zuständen trennen Strings der Länge n mit positiver Wahrscheinlichkeit (oder vielleicht Wahrscheinlichkeit ≥ 1 / 2 )? Eine kurze Suche ergab nicht viele Ergebnisse zu den Eigenschaften zufälliger DFAs. Ich konnte nur http://arxiv.org/abs/1311.6830 finden .$f(n)$$f(n)$$n$$\ge 1/2$

[Bearbeiten: Diese Antwort funktioniert nicht, siehe Kommentare.]

Dies ist nur eine informelle Idee und ich weiß nicht, ob es hilft, aber es ist zu lang, um als Kommentar gegeben zu werden. Außerdem kenne ich mich mit zufälligen DFAs überhaupt nicht aus. Vielleicht habe ich eine falsche Vorstellung davon, wie Sie mit Wahrscheinlichkeiten darüber argumentieren sollten, aber hoffentlich ist dies nicht ganz wertlos.

Ich gehe davon aus, dass Ihre Grenzen davon abhängen sollten, wie sehr sich und v unterscheiden. Wenn dies nicht der Fall ist, scheint mir klar zu sein, dass sich die Zeichenfolgen im schlimmsten Fall nur durch das erste Zeichen unterscheiden (Zeichenfolgen, die sich an einer Reihe von X Positionen unterscheiden, haben mehr Chancen, voneinander getrennt zu werden als Zeichenfolgen, die sich an einer Reihe unterscheiden)$u$$v$$X$ Positionen unterscheiden) Ich würde sagen, und wenn Sie den Unterschied so früh wie möglich setzen, haben Sie die Möglichkeit, ihn erneut zu synchronisieren.$Y \subset X$

Ich werde auch die Wahrscheinlichkeit untersuchen, dass die Wörter unterschieden werden, nämlich unterschiedliche Zustände erreichen. Ich denke, Sie müssten sich dann darauf einstellen, ob Sie akzeptiert oder abgelehnt werden, je nachdem, wie Ihre zufälligen DFAs die Endzustände zuweisen. Wenn jeder Zustand eine halbe Wahrscheinlichkeit hat, endgültig zu sein, werden die Saiten nicht unterschieden, wenn sie in demselben Zustand enden, und wenn sie in verschiedenen Zuständen enden, haben sie eine halbe Wahrscheinlichkeit, unterschieden zu werden.

Nun betrachte ich das Wort das aus u und v erhalten wird, wie folgt: w i = 1, wenn u i = v i und w i = 0, andernfalls. Ich denke, es ist klar, dass w das einzig Interessante an u und v ist .$w$$u$$v$$w_i = 1$$u_i = v_i$$w_i = 0$$w$$u$$v$

Definieren Sie nun die Wahrscheinlichkeit, dass wir nach dem Lesen von Präfixen der Länge i von u und v im selben Zustand sind , und q ( i ) = 1 - p $p(i)$$i$$u$$v$ die Wahrscheinlichkeit, dass wir nichtsind.$q(i) = 1 - p(i)$

Ich denke wir haben , wenn w i + 1 ist 1 . Intuitiv befinden wir uns nach dem Lesen von i + 1 Buchstaben im selben Zustand, entweder als wir uns nach dem Lesen von i im selben Zustand befanden, oder als wir uns in zwei verschiedenen (zufälligen) Zuständen befanden, zeichneten wir zwei Übergänge in zufällige Zustände und sie passierten sei der gleiche. Ebenso haben wir p ( i + 1 ) = $p(i+1) = p(i) + q(i)/n$$w_{i+1}$$1$$i+1$$i$ , wenn w i + 1 ist 0 : Sie zeichnen zwei zufällige Zustände, unabhängig davonwo Sie begonnen.$p(i+1) = 1/n$$w_{i+1}$$0$

Daraus könnte man die Wahrscheinlichkeit berechnen, dass man sich nach dem Lesen von und v im selben Zustand befindet .$u$$v$