Количество разных обычных языков

Учитывая алфавит , сколько существует различных регулярных языков, которые могут быть приняты недетерминированным конечным автоматом с n состояниями?$\Sigma = \{ a,b \}$$n$

В качестве примера рассмотрим . Затем у нас есть 2 18 различных конфигураций перехода и 2 3 различных конфигурации начального и конечного состояний, поэтому у нас есть верхняя граница 2 24 различных языков. Тем не менее, многие из них будут эквивалентны, и, поскольку тестирование для этого является PSPACE-Complete, возможно, невозможно проверить каждый параметр. Существуют ли другие средства или комбинаторные аргументы, которые ограничивают количество различных языков, принятых данным ресурсом?$n=3$$2^{18}$$2^3$$2^{24}$

Это краткое изложение статьи « О количестве отдельных языков, принятых конечными автоматами с n государствами» . В документе даны относительно простые, но далеко не жесткие, нижние и верхние границы количества различных языков, принятых NFA. Их обсуждение количества различных DFA очень проницательно, поэтому я также включу эту часть.

Статья начинается с довольно строгой асимптотики для числа различных языков, принятых DFA с состояниями над унарным алфавитом. Это делается путем наблюдения , при каких условиях данного п -state унарного DFA минимален. В таких случаях описание автомата может быть сопоставлено (биективно) с примитивным словом , а перечисление таких слов хорошо известно и выполняется с помощью функции Мёбиуса . Используя этот результат, границы для неунарных алфавитов, как в DFA, так и в случае NFA, доказаны.$n$$n$

Давайте углубимся в детали. Для буквенного алфавита определите f k ( n $k$ ЗаметимчтогК(п)=Е п я = 1 фК(я). Начнем сf1(k)иg1(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)$

Перечень унарных ДФА

Унарный DFA с состояниями q 0 , … , q n - 1 минимален тогда и только тогда, когда$M = (Q, \{a\},\delta, q_0,F)$$q_0,\dots, q_{n-1}$

1. Это связано. Таким образом, после переименования диаграмма перехода состоит из петли и хвоста, т.е. и δ ( q n - 1 , a ) = q j для некоторого j ≤ n - 1 ,$\delta(q_i,a) = q_{i+1}$$\delta(q_{n-1},a)=q_j$$j \leq n-1$
2. Цикл минимален.
3. Если , то либо д J - 1 ∈ F и Q п - 1 ∉ F или д J - 1 ∉ F и Q п - 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$

Цикл минимален тогда и только тогда, когда слово a j ⋯ a n - 1 определено как a i = { $q_j,\dots, q_{n-1}$$a_j \cdots a_{n-1}$ являетсяпримитивной, что означаетчто не может быть записана в видехK для некоторого словахи некоторого целого числак≥2. Числоψk(n)примитивных слов длинойnнадбуквамиk-буквы известно, см., Например, Lothaire,Combinatorics on Words. Мы имеем ψ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$ гдеμ(n)-функция Мёбиуса. С помощью ψ k (n)в статье доказываются точные формулы для f 1 (n)и g 1 (n)и показано, что асимптотически (теорема 5 и следствие 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*}$$

Перечень ДФА

Следующим шагом является оценка снизу для . Теорема 7 утверждает, что f k ( n ) ≥ f 1 ( n ) n ( k - 1 ) n ∼ n $f_k(n)$ Для множестваΔ⊂ΣавтоматаMопределим M Δ как ограничениеMнаΔ.

$$\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$
Доказательство работает путем рассмотрения множества M DFA над алфавитом k- буквы { 0 , 1 , … , k - 1 }, определенным как$S_{k,n}$$M$$k$$\{0,1,\dots,k-1 \}$

1. Пусть будет одним из f 1 ( n ) различных унарных DFA на n состояний, и$M_{ \{0 \}}$$f_1(n)$$n$
2. Выбор любой функции h i : Q → Q для 1 $k-1$$h_i : Q \to Q$$1 \le i < k$$\delta(q,i) = h_i(q)$$1 \le i < k$$q \in Q$

Наблюдение тогда состоит в том, что содержит f 1 ( n ) n ( k - 1 ) n разных и минимальных языков.$S_{n,k}$$f_1(n) n^{ (k-1)n}$

Перечень НФА

Для каждый имеет тривиальную нижнюю оценку 2 n , поскольку любое подмножество ϵ , a , … , a n - 1 может быть принято некоторым NFA с n состояниями. Нижняя граница немного улучшена, но доказательство довольно длинное. В статье Описательная сложность в унарном случае Померанса и др. Показано, что G 1 ( n ) ≤ ( c 1$G_1(n)$$2^n$$\epsilon, a,\dots, a^{n-1}$$n$
. Предложение 10 показывает, что дляk≥2имеем n2(k-1)n2≤Gk(n)≤(2n-1)2kn2+1. Доказательство довольно короткое, поэтому я включаю его дословно (более или менее). Для верхней границы обратите внимание, что любой NFA можно указать, указав для каждой пары(q,a$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*}$$ 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.