O número de diferentes idiomas regulares

Dado um alfabeto $\Sigma = \{ a,b \}$ , quantas linguagens regulares diferentes existem que podem ser aceitas por um autômato finito não-determinístico do estado ?$n$

Como exemplo, vamos considerar . Temos então configurações de transição diferentes e configurações diferentes de estado inicial e final, portanto, temos um limite superior de idiomas diferentes. No entanto, muitos deles serão equivalentes e, uma vez que o teste é PSPACE-Complete, provavelmente não é possível testar cada configuração. Existem outros meios ou argumentos combinatórios que vinculam o número de idiomas diferentes aceitos por um determinado recurso?2 18 2 3 2 $n=3$$2^{18}$$2^3$$2^{24}$

Este é um resumo do artigo Sobre o número de idiomas distintos aceitos pelos autômatos finitos com n Estados . O documento fornece limites relativamente fáceis, porém distantes, reduzidos e superiores do número de idiomas distintos aceitos pelos NFAs. A discussão deles sobre o número de DFAs distintos é muito esclarecedora, por isso também incluirei essa parte.

O artigo começa com um assintótico bastante rigoroso para o número de idiomas distintos aceitos por um DFA com estados em um alfabeto unário. Isso é feito observando sob quais condições um determinado DFA de estado n unário é mínimo. Nesses casos, a descrição do autômato pode ser mapeada (bijetivamente) para uma palavra primitiva , e a enumeração de tais palavras é bem conhecida e feita com a ajuda da função Möbius . Usando esse resultado, os limites para alfabetos não unários, tanto no caso do DFA quanto no do NFA, são comprovados.$n$$n$

Vamos entrar em mais detalhes. Para um alfabeto com letras , defina f k ( n $k$ Observe quegk(n)=∑

$$\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*}$$ . Começamos comf1(k)eg1(k). $g_k(n) = \sum_{i=1}^n f_k(i)$$f_1(k)$$g_1(k)$

Enumeração de DFAs unários

Um DFA unário com estados q 0 , … , q n - 1 é mínimo se$M = (Q, \{a\},\delta, q_0,F)$$q_0,\dots, q_{n-1}$

1. Está conectado. Assim, após renomear, o diagrama de transição consiste em um loop e uma cauda, ​​ou seja, eδ( q n - 1 ,a)= q j para algunsj≤n-1.$\delta(q_i,a) = q_{i+1}$$\delta(q_{n-1},a)=q_j$$j \leq n-1$
2. O loop é mínimo.
3. Se , então q j - 1 ∈ F e $j \neq 0$$q_{j-1} \in F$ou q j - 1 ∉Fe q n - 1 ∈F.$q_{n-1} \notin F$$q_{j-1} \notin F$$q_{n-1} \in F$

O loop é mínimo se a palavra a j ⋯ a n - 1 definida por a i = { $q_j,\dots, q_{n-1}$$a_j \cdots a_{n-1}$ forprimitivo, o que significa que não pode ser escrito na formaxk para alguma palavraxe algum número inteirok≥2. O númeroψk(n)de palavras primitivas de comprimentonsobrekd, em queμ(n)é afunção Möbius. Com a ajuda deψk(n

$$\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$ alfabetos com letra é conhecido, ver, por exemplo, Lothaire, Combinatorics on Words . Temos $$\begin{equation*} \psi_k(n) = \sum_{d | n} \mu(d) k^{n/d} \end{equation*}$$ $\mu(n)$$\psi_k(n)$ o papel prova fórmulas exactas para e g 1 ( n ) e mostra que assintoticamente (Teorema 5 e Corollary 6), g 1 ( 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*}$$

Enumeração de DFAs

O próximo passo é um limite inferior para . O teorema 7 afirma que f k ( n ) ≥ f 1 ( n ) n ( k - 1 ) n ∼ n 2 n - 1 n ( k - 1 ) n . Para um conjunto Δ ⊂ Σ de um autômato M , defina M Δ como a restrição de M a Δ .$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$
A prova funciona considerando o conjunto $S_{k,n}$ de do DFA sobre o k -Carta alfabeto { 0 , 1 , ... , k - 1 } definida por$M$$k$$\{0,1,\dots,k-1 \}$

1. Permitir que seja um dos f 1 ( n ) DFAs unários diferentes em n estados e$M_{ \{0 \}}$$f_1(n)$$n$
2. Escolhendo quaisquer funções h i : Q → Q para 1 ≤ i < k e definindo δ ( q , i ) $k-1$$h_i : Q \to Q$$1 \le i < k$ para um ≤ i < k e q ∈ Q .$\delta(q,i) = h_i(q)$$1 \le i < k$$q \in Q$

A observação é então que contém f 1 ( n ) n ( k - 1 ) n línguas diferentes e mínimas.$S_{n,k}$$f_1(n) n^{ (k-1)n}$

Enumeração de AFN

Para um tem o limite inferior trivial 2 n , já que todo subconjunto ϵ , a , … , a n - 1 pode ser aceito por algum NFA com $G_1(n)$$2^n$$\epsilon, a,\dots, a^{n-1}$$n$
$G_1(n) \le \left( \frac{c_1 n}{\log n}\right)^n$
$k \ge 2$

$$\begin{equation*} n 2^{(k-1)n^2} \le G_k(n) \le (2n-1) 2^{kn^2} +1. \end{equation*}$$ $(q,a)$$Q$$\delta(q,a)$$2^{kn^2}$$\{1,\dots,k\}$$k \in [0..n-1]$
$M=(Q,\Sigma,\delta,q_0, F)$$\Sigma = \{ 0,1,\dots,k-1 \}$$Q=\{ q_0,\dots, q_{n-1} \}$$\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*}$$ $h_j: \{ 1,\dots,n-1\} \to 2^Q$$F=\{q_i\}$$i \in [0..n-1]$$2^{(k-1)n^2}$$n$maneiras de escolher o conjunto de estados finais. Pode-se então mostrar que nenhum desses NFAs aceita o mesmo idioma.