Wie viele Sprachen werden von einem DFA der Größe

19

Die Frage ist einfach und direkt: Für ein festes , wie viele (verschiedene) Sprachen werden von einem DFA der Größe n (dh n Zustände) akzeptiert ? Ich werde dies formell erklären:nnn

Definieren Sie eine DFA als , wobei alles wie gewohnt ist und δ : Q × Σ Q eine (möglicherweise partielle) Funktion ist. Wir müssen dies feststellen, da manchmal nur Gesamtfunktionen als gültig betrachtet werden.(Q,Σ,δ,q0,F)δ:Q×ΣQ

Definieren Sie für jedes die (Äquivalenz-) Beziehung n auf der Menge aller DFAs als: A n B if | A | = | B | = n und L ( A ) = L ( B ) .n1nAnB|A|=|B|=nL(A)=L(B)

Die Frage ist dann: für ein gegebenes , was ist der Index von n ? Das heißt, wie groß ist die Menge { L ( A ) A  ist ein DFA der Größe  n } ?nn{L(A)A is a DFA of size n}

Selbst wenn eine Gesamtfunktion ist, scheint es keine einfache Zählung zu sein (zumindest für mich). Die Grafik kann nicht angeschlossen werden, und die Zustände in der angeschlossenen Komponente den Anfangszustand mit allen, könnte die Annahme so zum Beispiel gibt es viele Graphen der Größe n akzeptieren Σ * . Gleiches gilt für andere triviale Kombinationen für die leere Sprache und für andere Sprachen, deren minimaler DFA weniger als n Zustände hat.δnΣn

(Eine naive) Rekursion scheint auch nicht zu funktionieren. Wenn wir einen DFA der Größe und einen neuen Zustand hinzufügen, müssen wir einen Übergang entfernen, um den neuen Zustand zu verbinden In diesem Fall können wir die Originalsprache verlieren.k

Irgendwelche Gedanken?

Hinweis. Ich habe die Frage erneut aktualisiert, mit einer formellen Aussage und ohne die vorherigen ablenkenden Elemente.

Janoma
quelle
Zur Verdeutlichung: Meinen Sie "Wie viele verschiedene Sprachen kann man mit Zuständen definieren ?", Wobei eine Sprache mit n Zuständen definiert wird , wenn es einen DFA mit n Zuständen gibt, der dies akzeptiert. Auch für die regulären Ausdrücke hat der reguläre Ausdruck "a * aaaaaa" sicherlich> 1 Verkettungen, aber der DFA benötigt nur einen Status (zwei, wenn Sie eine separate Senke benötigen), nicht wahr? nnn
Evgenij Thorstensen
Apologies: Für die regex Beispiel sollte es sein „a a a a a *“, so dass eine beliebige Anzahl zulässt.
Evgenij Thorstensen
Die Definition von scheint sehr mit dem Begriff "Punkttiefe" verwandt zu sein, mit der Ausnahme, dass dieses Konzept normalerweise auf sternfreie Sprachen angewendet wird (wahrscheinlich aus den Gründen, die @Evgenij Thorstensen darlegte). c(r)
mhum
1
Triviale Beobachtung: Mit Zuständen können mindestens 2 n definiert werdenn+12n verschiedene Sprachen definiert werden.
Evgenij Thorstensen
2
Wir können ein bisschen mehr bekommen, also scheint Ordnung zu sein. Aber die Anzahl der Automaten mit n Zuständen liegt bei n c n 2 n = 2 c n log n + n = 2 Θ ( n log n ) (unter der Annahme von | Σ | = c ). Können wir 2 ω ( n ) bekommen ? 2Ω(n)ncn2n=2cnlogn+n=2Θ(nlogn)|Σ|=c2ω(n)
Kaveh

Antworten:

20

Ich denke, dass diese Frage zuvor untersucht wurde. Mike Domaratzki schrieb eine Umfrage zur Forschung in diesem Bereich: "Aufzählung der formalen Sprachen", Bull. 5-1997, Ziff. EATCS, vol. 89 (Juni 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

Hermann Gruber
quelle
4
Das Papier behandelt genau die gestellte Frage ab Seite 120. Es ist die Funktion , und das Papier enthält ziemlich enge Grenzen (in der Nähe dessen, was Kaveh oben erwähnt hat), obwohl ich nicht alle Details inhaliert habe. gk(n)
Evgenij Thorstensen
1
gk(n)fk(n)nk
6
Und vom selben Autor haben wir den Artikel Über die Anzahl der von endlichen Automaten akzeptierten unterschiedlichen Sprachen mit n Zuständen , der sogar explizite Berechnungen für liefert.g1(n)1n10g2(n)1n6) and g3(n) (1n4).
Janoma