Jumlah bahasa reguler yang berbeda

Diberi alfabet $\Sigma = \{ a,b \}$ , berapa banyak bahasa reguler yang berbeda yang dapat diterima oleh otomat terbatas non-deterministik $n$ -negara?

Sebagai contoh, mari kita pertimbangkan $n=3$ . Kami kemudian memiliki $2^{18}$ konfigurasi transisi yang berbeda dan $2^3$ konfigurasi awal dan akhir yang berbeda, jadi kami memiliki batas atas $2^{24}$ bahasa yang berbeda.
Namun, banyak dari ini akan setara dan karena pengujian untuk itu adalah PSPACE-Complete, mungkin tidak layak untuk menguji setiap pengaturan.
Adakah argumen sarana atau kombinatorial lain yang mengikat jumlah bahasa berbeda yang diterima oleh sumber daya yang diberikan?

Ini adalah ringkasan makalah tentang Jumlah Bahasa yang Berbeda yang Diterima oleh Finite Automata dengan n Negara . Makalah ini menyediakan relatif mudah, namun jauh dari batas ketat, bawah dan atas pada jumlah bahasa berbeda yang diterima oleh NFA. Diskusi mereka tentang jumlah DFA yang berbeda sangat mendalam, jadi saya juga akan memasukkan bagian itu.

Makalah ini dimulai dengan asimtotik yang cukup ketat untuk jumlah bahasa berbeda yang diterima oleh DFA dengan menyatakan lebih dari alfabet unary. Hal ini dilakukan dengan mengamati di bawah kondisi DFA n-negara unary tertentu minimal. Dalam kasus seperti itu deskripsi otomaton dapat dipetakan (secara objektif) ke kata primitif , dan penghitungan kata-kata tersebut diketahui dan dilakukan dengan bantuan fungsi Möbius . Dengan menggunakan hasil itu, batas untuk huruf non-unary, baik dalam DFA dan dalam kasus NFA, terbukti.$n$$n$

Mari kita bahas lebih detail. Untuk alfabet newsletter, tentukan f k ( n $k$ Perhatikan bahwagk(n)=Σ n i = 1 fk(i). Kita mulai denganf1(k)dang1(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)$

Pencacahan DFA Unary

DFA unary ( Q , { a } , δ , q 0 , F ) dengan status q 0 , ... , q n - 1 minimal iff$M = (Q, \{a\},\delta, q_0,F)$$q_0,\dots, q_{n-1}$

1. Terhubung. Dengan demikian, setelah penggantian nama, diagram transisi terdiri dari satu lingkaran dan satu ekor, yaitu dan δ ( q n - 1 , a ) = q j untuk beberapa j ≤ n - $\delta(q_i,a) = q_{i+1}$$\delta(q_{n-1},a)=q_j$$j \leq n-1$ .
2. Loopnya minimal.
3. Jika , maka baik q j - 1 ∈ F dan q n - 1 ∉ F atau q j - 1 ∉ F dan 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$

Loop minimal IFF kata seorang j ⋯ sebuah n - 1 didefinisikan oleh sebuah i = { $q_j,\dots, q_{n-1}$$a_j \cdots a_{n-1}$ adalahprimitif, yang berarti tidak dapat ditulis dalam bentukxk untuk beberapa kataxdan beberapa bilangan bulatk≥2. Jumlahψk(n)kata-kata primitif dengan panjangn diatashurufk-newsletter diketahui, lihat misalnya Lothaire,Combinatorics on Words. Kami memiliki ψ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$ manaμ(n)adalahfungsi Möbius. Dengan bantuan ψ k (n), makalah ini membuktikan formula yang tepat untuk f 1 (n)dan g 1 (n)dan menunjukkan bahwa asimtotik (Teorema 5 dan Konsol 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*}$$

Pencacahan DFA

Langkah selanjutnya adalah batas bawah untuk . Teorema 7 menyatakan bahwa f k ( n ) ≥ f 1 ( n ) n ( k - 1 ) n ~ n 2 n - 1 n ( k - 1 ) n . Untuk set Δ ⊂ Σ dari otomat M , tentukan M Δ sebagai batasan M ke $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$$q \in Q$.

The observation is then that $S_{n,k}$ mengandung $f_1(n) n^{ (k-1)n}$ bahasa yang berbeda dan minimal.

Pencacahan NFA

Untuk $G_1(n)$ seseorang memiliki batas bawah yang sepele $2^n$, karena setiap subset $\epsilon, a,\dots, a^{n-1}$ dapat diterima oleh beberapa NFA dengan $n$menyatakan. Batas bawah sedikit ditingkatkan, namun buktinya agak panjang.
Makalah Kompleksitas Deskriptif dalam kasus unary oleh Pomerance et al menunjukkan itu$G_1(n) \le \left( \frac{c_1 n}{\log n}\right)^n$.
Proposisi 10 menunjukkan bahwa, untuk$k \ge 2$ kita punya

$$\begin{equation*} n 2^{(k-1)n^2} \le G_k(n) \le (2n-1) 2^{kn^2} +1. \end{equation*}$$ Buktinya cukup singkat, maka saya memasukkannya kata demi kata (kurang lebih). Untuk batas atas, perhatikan bahwa NFA dapat ditentukan dengan menentukan, untuk setiap pasangan$(q,a)$ negara dan simbol, yang bagian dari $Q$ sama dengan $\delta(q,a)$ (karenanya faktornya $2^{kn^2}$. Kami dapat menetapkan status akhir sebagai berikut: apakah kondisi awal adalah final atau tidak, dan karena nama-nama negara tidak penting, kami dapat mengasumsikan status akhir yang tersisa adalah$\{1,\dots,k\}$ untuk $k \in [0..n-1]$. Akhirnya, jika kami tidak memilih status akhir, kami memperoleh bahasa kosong.
Untuk batas bawah penulis melanjutkan dengan cara yang sama seperti pada bukti untuk kasus DFA: Tentukan NFA$M=(Q,\Sigma,\delta,q_0, F)$ dengan $\Sigma = \{ 0,1,\dots,k-1 \}$, $Q=\{ q_0,\dots, q_{n-1} \}$ dan $\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.