Die Anzahl der verschiedenen regulären Sprachen

Gegeben ein Alphabet $\Sigma = \{ a,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 $2^{18}$ verschiedene Übergangskonfigurationen und $2^3$ verschiedene Start- und Endzustandskonfigurationen, sodass wir eine Obergrenze von $2^{24}$ 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?

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.$n$$n$

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).

$$\begin{align*} f_k(n) &= \text{the number of pairwise non-isomorphic minimal DFA's with } n \text{ states}\\ g_k(n) &= \text{the number of distinct languages accepted by DFA's with } n \text{ states}\\ G_k(n) &= \text{the number of distinct languages accepted by NFA's with } n \text{ states} \end{align*}$$ $g_k(n) = \sum_{i=1}^n f_k(i)$$f_1(k)$$g_1(k)$

Aufzählung der unären DFAs

Ein unärer DFA $M = (Q, \{a\},\delta, q_0,F)$ mit den Zuständen ist minimal, wenn$q_0,\dots, q_{n-1}$

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 .$\delta(q_i,a) = q_{i+1}$$\delta(q_{n-1},a)=q_j$$j \leq n-1$
2. Die Schleife ist minimal.
3. Wenn , dann ist entweder q j - 1 ≤ F und q n - 1 ≤ F oder q j - $j \neq 0$$q_{j-1} \in F$$q_{n-1} \notin F$ und q n - 1 ∈ F .$q_{j-1} \notin F$$q_{n-1} \in F$

Die Schleife ist minimal, wenn das Wort a j ⋯ a n - 1 durch a i = { $q_j,\dots, q_{n-1}$$a_j \cdots a_{n-1}$ istprimitiv, das heißtsie können nicht in der Form geschrieben werdenxk für einige Wortxund einige ganze Zahlk≥2. 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

$$\begin{equation*} a_i = \begin{cases} 1 \quad \text{if } q \in F, \\ 0 \quad \text{if } q \notin F \end{cases} \end{equation*}$$ $x^k$$x$$k \ge 2$
$\psi_k(n)$$n$$k$ wobeiμ(n)dieMöbius-Funktion ist $$\begin{equation*} \psi_k(n) = \sum_{d | n} \mu(d) k^{n/d} \end{equation*}$$ $\mu(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 $\psi_k(n)$$f_1(n)$$g_1(n)$ $$\begin{align*} g_1(n) &= 2^n \left(n-\alpha+O \left(n 2^{-n/2} \right)\right) \\ f_1(n) &= 2^{n-1}\left(n+1-\alpha+O \left(n 2^{-n/2} \right)\right). \end{align*}$$

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 ) n ≤ n 2 n - 1 n ( k - 1 ) n ist . Für einen Satz Δ ⊂ & Sigma; eines Automaten M definieren M Δ als Einschränkung des M zu Δ .$f_k(n)$

$$\begin{equation*} f_k(n) \ge f_1(n) n^{ (k-1)n} \sim n 2^{n-1}n^{(k-1)n}. \end{equation*}$$ $\Delta \subset \Sigma$$M$$M_{\Delta}$$M$$\Delta$
den Beweis Arbeiten des Satzes unter Berücksichtigung $S_{k,n}$$M$$k$$\{0,1,\dots,k-1 \}$

1. $M_{ \{0 \}}$$f_1(n)$$n$
2. $k-1$$h_i : Q \to Q$$1 \le i < k$$\delta(q,i) = h_i(q)$$1 \le i < k$$q \in Q$

Die Beobachtung ist dann die $S_{n,k}$ enthält $f_1(n) n^{ (k-1)n}$ verschiedene und minimale Sprachen.

Aufzählung der NFA

Zum $G_1(n)$ one has the trivial lower bound $2^n$, since every subset $\epsilon, a,\dots, a^{n-1}$ 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 $G_1(n) \le \left( \frac{c_1 n}{\log n}\right)^n$.
Proposition 10 shows that, for $k \ge 2$ we have

$$\begin{equation*} n 2^{(k-1)n^2} \le G_k(n) \le (2n-1) 2^{kn^2} +1. \end{equation*}$$ 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 $\delta(q,a)$ (hence the factor $2^{kn^2}$. 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,\dots,k\}$ for $k \in [0..n-1]$. 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,\Sigma,\delta,q_0, F)$ with $\Sigma = \{ 0,1,\dots,k-1 \}$, $Q=\{ q_0,\dots, q_{n-1} \}$ and $\delta$: $$\begin{align*} \delta(q_i,0) &=q_{(i+1) \mod n} \quad \text{for } 0 \le i <n \\ \delta(q_i,j) &=h_j(i) \quad \text{for } 0 \le i <n,\, 1 \le j < k \end{align*}$$ where $h_j: \{ 1,\dots,n-1\} \to 2^Q$ is any set-valued function. Finally, let $F=\{q_i\}$ for any $i \in [0..n-1]$. There are $2^{(k-1)n^2}$ 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.