Liczba różnych regularnych języków

Biorąc pod uwagę alfabet $\Sigma = \{ a,b \}$ , ile jest różnych języków regularnych, które może zaakceptować $n$ stanowy niedeterministyczny automat skończony?

Jako przykład rozważmy $n=3$ . Następnie mamy $2^{18}$ różnych konfiguracji przejścia i $2^3$ różne konfiguracje stanu początkowego i końcowego, więc mamy górną granicę $2^{24}$ różnych języków.
Jednak wiele z nich będzie równoważnych, a ponieważ testowanie pod kątem PSPACE-Complete jest prawdopodobnie niemożliwe przetestowanie każdego ustawienia.
Czy istnieją inne środki lub argumenty kombinatoryczne, które ograniczają liczbę różnych języków akceptowanych przez dany zasób?

To jest streszczenie artykułu O liczbie odrębnych języków akceptowanych przez skończone automaty z n stanami . Artykuł zapewnia stosunkowo łatwe, ale dalekie od ścisłych, dolnych i górnych granic liczbę różnych języków akceptowanych przez NFA. Ich dyskusja na temat liczby różnych DFA jest bardzo wnikliwa, więc uwzględnię również tę część.

Artykuł zaczyna się od dość rygorystycznej asymptotyki w odniesieniu do liczby różnych języków akceptowanych przez DFA, przy czym stanowi jednolity alfabet. Dokonuje się tego, obserwując, w jakich warunkach dany n- stanowy jednoargumentowy DFA jest minimalny. W takich przypadkach opis automatu może być odwzorowany (biotycznie) na prymitywne słowo , a wyliczenie takich słów jest dobrze znane i wykonane za pomocą funkcji Möbiusa . Korzystając z tego wyniku, udowodniono granice dla jednych alfabetów, zarówno w przypadku DFA, jak i przypadku NFA.$n$$n$

Przejdźmy bardziej szczegółowo. Dla alfabetu -liter zdefiniuj f k ( n $k$ Zwróć uwagę, żegk(n)=∑ n i = 1 fk(i). Rozpoczynamy odf1(k)ig1(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)$

Wyliczenie Unary DFA

Jednostkowy DFA ze stanami q 0 , … , q n - 1 jest minimalny iff$M = (Q, \{a\},\delta, q_0,F)$$q_0,\dots, q_{n-1}$

1. Jest podłączony. Tak więc, po zmianie nazwy, schemat przejściowy składa się z pętli i ogona, tj. i δ ( q n - 1 , a ) = q j dla niektórych j ≤ n - 1 .$\delta(q_i,a) = q_{i+1}$$\delta(q_{n-1},a)=q_j$$j \leq n-1$
2. Pętla jest minimalna.
3. Jeśli , wówczas q j - 1 ∈ F i q n - 1 ∉ F i q j - 1 ∉ F i q n - 1 ∈ F .$j \neq 0$$q_{j-1} \in F$$q_{n-1} \notin F$$q_{j-1} \notin F$$q_{n-1} \in F$

Pętla jest minimalne IFF słowa j ⋯ n - 1 określa się I = { $q_j,\dots, q_{n-1}$$a_j \cdots a_{n-1}$ jestprymitywne, co oznacza, że ​​nie można go zapisać w formiexk dla jakiegoś słowaxi jakiejś liczby całkowitejk≥2. Znana jest liczbaψk(n)prymitywnych słów o długościnpowyżejk-liter alfabetu, patrz np. Lothaire,Combinatorics on Words. Mamy ψ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$ gdzieμ(n)jestfunkcją Möbiusa. Dzięki * F k (n),papier dowodzi dokładnie formuły f 1 (n)i g 1 (n)i pokazuje, że asymptotycznie (twierdzenie 5, wynikiem czego 6) g 1 ( n $$\begin{equation*} \psi_k(n) = \sum_{d | n} \mu(d) k^{n/d} \end{equation*}$$ $\mu(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*}$$

Wyliczenie DFA

Następnym krokiem jest dolna granica dla . Twierdzenie 7 stwierdza, że f k ( n ) ≥ f 1 ( n ) n ( k - 1 ) n ∼ n 2 n - 1 n ( k - 1 ) n . Dla zestawu Æ ⊂ Ď z automatem M zdefiniować M Æ jako ograniczenie M do hemibursztynianu .$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$
$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$ and $q \in Q$.

The observation is then that $S_{n,k}$ contains $f_1(n) n^{ (k-1)n}$ different and minimal languages.

Enumeration of NFA's

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