Finden Sie den kleinsten DFA, der zwei Wörter ohne Brute-Force-Suche trennt?

Mit zwei Zeichenfolgen x und y möchte ich einen DFA mit einer Mindestgröße erstellen, der x akzeptiert und y ablehnt. Eine Möglichkeit hierfür ist die Brute-Force-Suche. Sie zählen die DFAs beginnend mit den kleinsten auf. Sie probieren jeden DFA aus, bis Sie einen finden, der x akzeptiert und y ablehnt.

Ich möchte wissen, ob es eine andere bekannte Möglichkeit gibt, einen DFA mit einer Mindestgröße zu finden oder zu erstellen, der x akzeptiert und y ablehnt. Mit anderen Worten, können wir die Brute-Force-Suche schlagen?

Mehr Details:

(1) Ich möchte wirklich, dass ein Algorithmus eine minimale DFA-Größe findet, keine nahezu minimale DFA-Größe.

(2) Ich möchte nicht nur wissen, wie groß oder klein der minimale DFA ist.

(3) Hier konzentriere ich mich nur auf den Fall, in dem Sie zwei Zeichenfolgen x und y haben.

Bearbeiten :

Zusätzliche Informationen für den interessierten Leser:

Angenommen, und y sind binäre Zeichenfolgen mit einer Länge von höchstens n . Es ist bekannt, dass es einen DFA gibt, der x akzeptiert und y mit höchstens √ ablehnt$x$$y$$n$$x$$y$ Staaten. Beachten Sie, dass es ungefährn$\sqrt{n}$ DFAs mit einem binären Alphabet und höchstens$n^{\sqrt{n}}$ Staaten. Daher würde der Brute-Force-Ansatz nicht erfordern, dass wir mehr alsn √ aufzählen$\sqrt{n}$ DFAs. Daraus folgt, dass der Brute-Force-Ansatz nicht viel mehr alsn √ dauern kann$n^{\sqrt{n}}$$n^{\sqrt{n}}$ zeit.

Folien, die ich hilfreich fand: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf

Wenn ich dies in der Praxis tun müsste, würde ich einen SAT-Löser verwenden.

Die Frage, ob es einen DFA mit Zuständen gibt, der x akzeptiert und y ablehnt, kann leicht als SAT-Instanz ausgedrückt werden. Zum Beispiel besteht eine Möglichkeit darin, 2 k 2 boolesche Variablen zu haben: z s , b , t ist wahr, wenn der DFA beim Eingangsbit b vom Zustand s zum Zustand t übergeht . Fügen Sie dann einige Klauseln hinzu, um zu erzwingen, dass dies ein DFA ist, und einige Variablen und Klauseln, um zu erzwingen, dass es x akzeptiert und y ablehnt .$k$$x$$y$$2k^2$$z_{s,b,t}$$s$$t$$b$$x$$y$

Verwenden Sie nun binäre Suche auf die kleinste zu finden k , so dass ein DFA dieser Art existiert. Basierend auf dem, was ich in Artikeln über verwandte Probleme gelesen habe, würde ich erwarten, dass dies in der Praxis einigermaßen effektiv ist.$k$$k$

Andere Kodierungen davon als SAT sind möglich. Beispielsweise können wir eine Ablaufverfolgungscodierung verwenden:

• Wenn Länge m hat , können Sie m lg k boolesche Variablen hinzufügen : Sei s 0 , s 1 , ... , s m die Folge von Zuständen, die am Eingang x durchlaufen werden , und repräsentieren jedes s i mit ⌈ lg k ⌉ booleschen Variablen.$x$$m$$m\lg k$$s_0,s_1,\dots,s_m$$x$$s_i$$\lceil \lg k \rceil$

• Nun haben Sie für jedes so dass x i = x j ist , die Bedingung, dass s i - 1 = s j - $i,j$$x_i=x_j$$s_{i-1}=s_{j-1} \implies s_i=s_j$ .

• Als nächstes erweitern Sie dies, um zu behandeln : sei t 0 , ... , t n die Folge von Zuständen, die an der Eingabe y durchlaufen werden , und repräsentieren jedes t j unter Verwendung von lg k booleschen Variablen. Fügen Sie für jedes i , j, so dass y i = y j ist, die Bedingung hinzu, dass t i - 1 = t j - $y$$t_0,\dots,t_n$$y$$t_j$$\lg k$$i,j$$y_i=y_j$ .$t_{i-1}=t_{j-1} \implies t_i=t_j$

• In ähnlicher Weise füge für jedes so dass x i = y j ist, die Bedingung hinzu, dass s i - 1 = t j - $i,j$$x_i=y_j$ .$s_{i-1}=t_{j-1} \implies s_i=t_j$

• Beide Messkurven müssen vom selben Startpunkt ausgehen. Fügen Sie daher die Anforderung hinzu, dass (WLOG kann s 0 = t 0 = 0 sein ).$s_0=t_0$$s_0=t_0=0$

• $k$$0 \le s_i < k$$0 \le t_j <k$$i,j$

• $x$$y$$s_m \ne t_n$

Alle diese Anforderungen können als SAT-Klauseln kodiert werden.

$k$$k$