Die Anzahl der verschiedenen regulären Sprachen

14

Gegeben ein Alphabet Σ={ein,b} , wie viele verschiedene reguläre Sprachen gibt es , dass durch ein akzeptiert werden kann n -state nicht-deterministischen endlichen Automaten?

Betrachten wir als Beispiel n=3 . Wir haben dann 218 verschiedene Übergangskonfigurationen und 23 verschiedene Start- und Endzustandskonfigurationen, sodass wir eine Obergrenze von 224 verschiedenen Sprachen haben.
Viele davon sind jedoch gleichwertig und da das Testen auf PSPACE-Complete erfolgt, ist es wahrscheinlich nicht möglich, jede Einstellung zu testen.
Gibt es andere Mittel oder kombinatorische Argumente, die die Anzahl der von einer bestimmten Ressource akzeptierten Sprachen begrenzen?

john_leo
quelle
Es gibt nur 3 verschiedene Startstatuskonfigurationen, nicht 23 .
FrankW
4
Schnelle Idee: Normale Sprachen zeichnen sich durch endlich viele Äquivalenzklassen aus, vgl. Myhill-Nerode. Wie viele verschiedene Sätze von Äquivalenzklassen kann ein Automat mit n Zuständen unterstützen?
Raphael
5
Es könnte hilfreich sein, nach dem Artikel "Über die Anzahl der von endlichen Automaten mit n Zuständen akzeptierten unterschiedlichen Sprachen" von Domaratzki, Kisman und Shallit zu suchen.
Hendrik Jan
1
hier ist die url
vzn
1
habe fast die gleiche Frage auf tcs.se gefunden: Wie viele Sprachen werden von einem DFA der Größe n akzeptiert?
VZN

Antworten:

11

Dies ist eine Zusammenfassung des Artikels Über die Anzahl der von endlichen Automaten akzeptierten unterschiedlichen Sprachen mit n Zuständen . Das Papier bietet relativ einfache, aber weit davon entfernt, enge Unter- und Obergrenzen für die Anzahl der von NFA akzeptierten unterschiedlichen Sprachen. Ihre Diskussion über die Anzahl der unterschiedlichen DFAs ist sehr aufschlussreich, daher werde ich auch diesen Teil einbeziehen.

Die Arbeit beginnt mit einer ziemlich strengen Asymptotik für die Anzahl der von einem DFA mit Zuständen über einem unären Alphabet akzeptierten unterschiedlichen Sprachen . Dies erfolgt durch Beobachten, unter welchen Bedingungen ein gegebener unärer n- Zustand-DFA minimal ist. In solchen Fällen kann die Beschreibung des Automaten (bijektiv) auf ein primitives Wort abgebildet werden , und die Aufzählung solcher Wörter ist bekannt und erfolgt mit Hilfe der Möbius-Funktion . Mit diesem Ergebnis werden Grenzen für nicht-unäre Alphabete sowohl im DFA- als auch im NFA-Fall bewiesen.nn

Lassen Sie uns näher darauf eingehen. Für ein -letter Alphabet definieren Sie f k ( n )k zu beachtendassgk(n)=Σ n i = 1 fk(i). Wir beginnen mitf1(k)undg1(k).

fk(n)=the number of pairwise non-isomorphic minimal DFA's with n statesgk(n)=the number of distinct languages accepted by DFA's with n statesGk(n)=the number of distinct languages accepted by NFA's with n states
gk(n)=i=1nfk(i)f1(k)g1(k)

Aufzählung der unären DFAs

Ein unärer DFA M=(Q,{a},δ,q0,F) mit den Zuständen ist minimal, wennq0,,qn1

  1. Es ist verbunden. Somit besteht das Übergangsdiagramm nach dem Umbenennen aus einer Schleife und einem Schwanz, dh und δ ( q n - 1 , a ) = q j für einige j n - 1 .δ(qi,a)=qi+1δ(qn1,a)=qjjn1
  2. Die Schleife ist minimal.
  3. Wenn , dann ist entweder q j - 1F und q n - 1F oder q j - 1j0qj1Fqn1F und q n - 1F .qj1Fqn1F

Die Schleife ist minimal, wenn das Wort a ja n - 1 durch a i = { 1 definiert istqj,,qn1ajan1 istprimitiv, das heißtsie können nicht in der Form geschrieben werdenxk für einige Wortxund einige ganze Zahlk2. Die Anzahlψk(n)von primitiven Wörtern der Längenüberk-Buchstaben-Alphabeten ist bekannt, siehe z. B. Lothaire,Combinatorics on Words. Wir haben ψk(n)=d | nμ(d)kn/

ai={1if qF,0if qF
xkxk2
ψk(n)nk wobeiμ(n)dieMöbius-Funktion ist
ψk(n)=d|nμ(d)kn/d
μ(n) . Mit Hilfe von liefert die Arbeit exakte Formeln für f 1 ( n ) und g 1 ( n ) und zeigt, dass asymptotisch (Satz 5 und Folgerung 6), g 1 ( n )ψk(n)f1(n)g1(n)
g1(n)=2n(nα+O(n2n/2))f1(n)=2n1(n+1α+O(n2n/2)).

Aufzählung der DFAs

Der nächste Schritt ist eine Untergrenze für . Satz 7 besagt, dass f k ( n ) f 1 ( n ) n ( k - 1 ) nn 2 n - 1 n ( k - 1 ) n ist . Für einen Satz Δ & Sigma; eines Automaten M definieren M Δ als Einschränkung des M zu Δ .fk(n)

fk(n)f1(n)n(k1)nn2n1n(k1)n.
ΔΣMMΔMΔ
den Beweis Arbeiten des Satzes unter Berücksichtigung Sk,nMk{0,1,,k1}
  1. M{0}f1(n)n
  2. k1hi:QQ1i<kδ(q,i)=hi(q)1i<kqQ

Die Beobachtung ist dann die Sn,k enthält f1(n)n(k-1)n verschiedene und minimale Sprachen.

Aufzählung der NFA

Zum G1(n) one has the trivial lower bound 2n, since every subset ϵ,a,,an1 can be accepted by some NFA with n states. The lower bound is improved slightly, yet the proof is rather lengthy.
The paper Descriptional Complexity in the unary case by Pomerance et al shows that G1(n)(c1nlogn)n.
Proposition 10 shows that, for k2 we have

n2(k1)n2Gk(n)(2n1)2kn2+1.
The proof is quite short, hence I include it verbatim (more or less). For the upper bound, note that any NFA can be specified by specifying, for each pair (q,a) of state and symbol, which subset of Q equals δ(q,a) (hence the factor 2kn2. We may assign the final states as follows: either the initial state is final or not, and since the names of the states are unimportant, we may assume the remaining final states are {1,,k} for k[0..n1]. Finally, if we choose no final states, we obtain the empty language.
For the lower bound the authors proceed in a similar way as in the proof for the DFA case: Define an NFA M=(Q,Σ,δ,q0,F) with Σ={0,1,,k1}, Q={q0,,qn1} and δ:
δ(qi,0)=q(i+1)modnfor 0i<nδ(qi,j)=hj(i)for 0i<n,1j<k
where hj:{1,,n1}2Q is any set-valued function. Finally, let F={qi} for any i[0..n1]. There are 2(k1)n2 such functions and n ways to choose the set of final states. One can then show that no two such NFA's accept the same language.
john_leo
quelle