Deterministische endliche Automaten zählen

Ich habe eine Frage zum Zählen von DFAs:

Wie würde ich bei einer Σ = {0, 1}Eingabezeichenfolge mit festgelegtem Status Q = {1...n}die Gesamtzahl der DFAs ermitteln, die erstellt werden können?

Ich glaube, dies ist ein kombinatorisches Problem, aber ich bin mir nicht sicher, was ich multiplizieren müsste.

Vielen Dank.

finite-automata combinatorics Heplar
quelle

Nicht ganz sicher, was Sie unter "konstruiert werden können" verstehen. Meinen Sie, ein DFA hat den Zustand 1, ein anderer die Zustände 1 und 2, ein anderer die Zustände 1, 2 und 3 usw.? In diesem Fall müssen Sie alle möglichen Teilmengen von 1 bis n Zuständen betrachten. Es gibt einen speziellen Namen dafür, aber ich lasse Sie es herausfinden.

Hinweis : Es kommt auch auf die Sprache an! Daher ist für jedes mögliche deterministische Übergangsdiagramm möglicherweise kein DFA der Sprache erforderlich. - Also nicht nur ein kombinatorisches Problem.

Grijesh Chauhan

Wollte antworten, aber es ist schwierig. Folgendes habe ich erhalten: Ein DFA wird durch eine Reihe von Zuständen, eine Reihe von Kanten von Zustand zu Zustand und den Anfangszustand definiert. Es ist also ein gerichteter Graph. Ein binärer DFA hat genau zwei Kanten von jedem Zustand. Jeder Zustand muss vom Ausgangszustand aus erreichbar sein. Dies ist eine stärkere Anforderung als "verbunden", aber schwächer als "stark verbunden".

Soll die Zustandsnummer eine beobachtbare Ausgabe sein? Ich würde denken, dass zwei DFAs mit derselben Topologie, aber unterschiedlich nummerierten Zuständen gleich wären. Aber es ist nicht klar aus der Frage. Es ist nicht zu beobachten, dies ist eine wirklich schwierige Frage, die eine Veröffentlichung verdient .

Dieses Problem wird hier nicht mathematisch / genau formuliert, aber eine sorgfältige / strenge Neuformulierung ist wahrscheinlich "tief". scheint ähnlich zu sein Graphisomorphie . Auch eine natürliche / offensichtliche Verallgemeinerung betrifft NFAs. Wie bei der Antwort von JEP ist es auch für einen empirischen / Monte-Carlo-Typ-Schätzungsansatz leicht zugänglich.

vzn

Antworten:

Dies ist in der Tat ein nicht triviales Problem. Eine Lösung finden Sie in diesem Dokument: Aufzählung und zufällige Generierung zugänglicher Automaten .

J.-E. Stift
quelle

Im Wesentlichen ist es das Produkt aller möglichen Übergänge von jedem möglichen Startzustand zu jedem möglichen Satz von Akzeptanzzuständen. Für dieses Beispiel gibt es n ^ (2n) Übergangsmöglichkeiten. Wo es n Gesamtzustände gibt, von denen jeder n mögliche Übergänge pro Kante hat (Eingabesymbol), was uns n ^ (2n) ergibt. Wir haben n mögliche Startzustände und 2 ^ n Akzeptanzzustände (die Potenzmenge möglicher Zustände). Das Produkt aller drei ergibt uns: n ^ (2n) * n * 2 ^ (n).

Heplar
quelle

Wenn Sie eine Kennzeichnung der Status von DFAs erzwingen, ist Ihre Antwort möglicherweise korrekt. Ohne Beschriftung (so wird ein DFA definiert) ist dies nicht korrekt. Sie müssen Startzustände berücksichtigen, da Sie jetzt überzählen. Stellen Sie sich einen DFA mit zwei Zuständen vor, dessen Übergänge für ein beliebiges Symbol in den anderen Zustand übergehen. Betrachten Sie den Fall mit zwei Akzeptanzzuständen (akzeptiert immer). Da es zwei Zustände gibt, gibt es zwei mögliche Startzustände. Diese beiden Maschinen sind jedoch genau gleich (Spiegelbilder voneinander). Wenn Sie die Zustände kennzeichnen, sind diese technisch unterschiedlich. Aber ohne sind diese DFAs gleich.

Mdxn

TL; DR: $n \centerdot 2^n \centerdot n^{mn}$

wo $\mid Q\mid$ $=$ $n$ und $\mid \Sigma\mid$ $=$ $m$ .

Wir werden jedes Element eines DFA-5-Tupels durchgehen, um die verschiedenen Kombinationen herauszufinden, die jeweils einen eindeutigen DFA ergeben würden. Das 5-Tupel besteht aus ( $Q$ , $\Sigma, \delta$ , $s$ , F)

$s$ ::

Beliebiges 1 Element von $Q$ kann der Startzustand sein. So gibt es $\mid Q\mid$ = $n$ Möglichkeiten zu wählen $s$ .

Eine beliebige Anzahl von Elementen von Q kann Akzeptanzzustände sein, daher sind alle Teilmengen von Q gültige Auswahlmöglichkeiten für F. Die Anzahl möglicher Teilmengen für eine Menge von Kardinalität n beträgt 2 $^n$ . Eine andere Möglichkeit, dies zu sagen, ist die Kardinalität von $Q$ ' $s$ Power Set $P(Q)$ ist 2 $^n$

$\delta$ ::

$\delta$ ist definiert als f: $Q$ x $\Sigma\rightarrow Q$ dh die $\delta$ Die Domäne der Funktion ist $Q$ x $\Sigma$ und seine Reichweite ist $Q$ . Die Kardinalität der Domain ist $mn$ wo $\mid Q\mid$ $=$ $n$ und $\mid \Sigma\mid$ $=$ $m$ und das des Bereichs ist $\mid Q\mid$ $=$ $n$ . So gibt es $n^{mn}$ Möglichkeiten zu wählen $\delta$ .

$Q$ und $\Sigma$ sind gegeben; da ist nur $1$ Weg, um sie zu wählen.

Also die Gesamtzahl der Möglichkeiten, unter den 5 Elementen eines DFA zu wählen, wo $\mid Q\mid$ $=$ $n$ und $\mid \Sigma\mid$ $=$ $m$ ist

$n \centerdot 2^n \centerdot n^{mn}$

Besser 5 Jahre zu spät als nie, oder?

JJ Skye
quelle

Sie sind technisch korrekt, aber ich denke, was OP bedeutete, war die Anzahl der verschiedenen Sprachen solcher DFAs, nicht die Anzahl der DFAs (aber ich könnte mich irren).

Ryan

In der Frage heißt es eindeutig: "Wie würde ich die Gesamtzahl der DFAs finden, die erstellt werden können?"

JJ Skye