El número de diferentes idiomas regulares.

Dado un alfabeto , ¿cuántos idiomas regulares diferentes puede aceptar un autómata finito no determinista de estados?$\Sigma = \{ a,b \}$$n$

Como ejemplo, consideremos . Luego tenemos configuraciones de transición diferentes y configuraciones de estado inicial y final diferentes, por lo que tenemos un límite superior de idiomas diferentes. Sin embargo, muchos de estos serán equivalentes y dado que la prueba para eso es PSPACE-Complete, probablemente no sea factible probar cada configuración. ¿Hay otros medios o argumentos combinatorios que limitan el número de idiomas diferentes aceptados por un recurso dado?$n=3$$2^{18}$$2^3$$2^{24}$

Este es un resumen del documento sobre el número de idiomas distintos aceptados por autómatas finitos con n estados . El documento proporciona límites relativamente fáciles, aunque lejos de ser estrictos, inferiores y superiores en cuanto al número de idiomas distintos aceptados por los NFA. Su discusión sobre el número de DFA distintos es muy perspicaz, por lo que también incluiré esa parte.

El artículo comienza con un asintótico bastante riguroso para la cantidad de idiomas distintos aceptados por un DFA con estados sobre un alfabeto unario. Esto se realiza observando en qué condiciones un DFA unario n dado es mínimo. En tales casos, la descripción del autómata puede asignarse (biyectamente) a una palabra primitiva , y la enumeración de tales palabras es bien conocida y se realiza con la ayuda de la función de Möbius . Usando ese resultado, se prueban los límites para alfabetos no unarios, tanto en el caso de DFA como en el de NFA.$n$$n$

Vamos a entrar en más detalles. Para un alfabeto -letter, defina f k ( n $k$ Tenga en cuenta quegk(n)=∑ n i = 1 fk(i). Comenzamos conf1(k)yg1(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)$

Enumeración de Dary unarios

Un DFA unario con estados q 0 , ... , q n - 1 es mínimo iff$M = (Q, \{a\},\delta, q_0,F)$$q_0,\dots, q_{n-1}$

1. Esta conectado. Por lo tanto, después de cambiar el nombre, el diagrama de transición consiste en un bucle y una cola, es decir, y δ ( q n - 1 , a ) = q j para algunos j ≤ n - 1 .$\delta(q_i,a) = q_{i+1}$$\delta(q_{n-1},a)=q_j$$j \leq n-1$
2. El bucle es mínimo.
3. Si , entonces o bien q j - 1 ∈ F y q n - 1 ∉ F o q j - 1 ∉ F y 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$

El ciclo es mínimo si la palabra a j ⋯ a n - 1 definida por a i = { $q_j,\dots, q_{n-1}$$a_j \cdots a_{n-1}$ esprimitivo, lo que significa que no se puede escribir en la formaxk para alguna palabraxyalgún enterok≥2. Seconoce elnúmeroψk(n)de palabras primitivas de longitudnsobrek-alfabetos de letras, véase, por ejemplo, Lothaire,Combinatorics on Words. Tenemos ψ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$ dondeμ(n)es lafunción de Möbius. Con la ayuda de ψ k (n),el documento prueba fórmulas exactas para f 1 (n)y g 1 (n)y muestra que asintóticamente (Teorema 5 y Corolario 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*}$$

Enumeración de DFA

El siguiente paso es un límite inferior para . El teorema 7 establece que f k ( n ) ≥ f 1 ( n ) n ( k - 1 ) n ∼ n 2 n - 1 n ( k - 1 ) n . Para un conjunto Δ ⊂ Σ de un autómata M , defina M Δ como la restricción 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$
La prueba funciona considerando el conjunto de M de DFA sobre el alfabeto k -letter { 0 , 1 , ... , k - 1 } definido por$S_{k,n}$$M$$k$$\{0,1,\dots,k-1 \}$

1. Dejar que sea ​​uno de los f 1 ( n ) diferentes DFA unarios en n estados, y$M_{ \{0 \}}$$f_1(n)$$n$
2. La elección de cualquier funciones h i : Q → Q para 1 ≤ i < k y que define δ ( q , i ) = h i ( q ) para 1 ≤ i < k y q ∈ Q .$k-1$$h_i : Q \to Q$$1 \le i < k$$\delta(q,i) = h_i(q)$$1 \le i < k$$q \in Q$

La observación es entonces que contiene f 1 ( n ) n ( k - 1 ) n idiomas diferentes y mínimos.$S_{n,k}$$f_1(n) n^{ (k-1)n}$

Enumeración de los NFA

$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$formas de elegir el conjunto de estados finales. Entonces se puede demostrar que no hay dos NFA que acepten el mismo idioma.