15
$\begingroup$

Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton?

As an example, let us consider $n=3$. We then have $2^{18}$ different transition configurations and $2^3$ different start- and end state configurations, so we have an upper bound of $2^{24}$ different languages.
However, many of these will be equivalent and since testing for that is PSPACE-Complete, it is probably unfeasible to test each setting.
Are there other means or combinatorial arguments that bound the number of different languages accepted by a given resource?

$\endgroup$
  • $\begingroup$ There are only 3 differnt start state configurations, not $2^3$. $\endgroup$ – FrankW May 8 '14 at 9:56
  • 4
    $\begingroup$ Quick idea: regular languages are characterised by finitely many equivalence classes, cf Myhill-Nerode. How many different sets of equivalence classes can an $n$-state automaton support? $\endgroup$ – Raphael May 8 '14 at 10:04
  • 5
    $\begingroup$ It might be helpful to google for the paper "On the number of distinct languages accepted by finite automata with n states" by Domaratzki, Kisman, and Shallit. $\endgroup$ – Hendrik Jan May 8 '14 at 16:27
  • 1
    $\begingroup$ here is the paper citeseer url $\endgroup$ – vzn May 8 '14 at 21:59
  • 1
    $\begingroup$ found nearly same question on tcs.se: What is the number of languages accepted by a DFA of size n? $\endgroup$ – vzn Jul 17 '14 at 15:10
11
$\begingroup$

This is a summary of the paper On the Number of Distinct Languages Accepted by Finite Automata with n States. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part.

The paper starts with a quite rigorous asymptotic for the number of distinct languages accepted by a DFA with $n$ states over a unary alphabet. This is done by observing under which conditions a given $n$-state unary DFA is minimal. In such cases the description of the automaton may be mapped (bijectively) to a primitive word, and the enumeration of such words is well-known and done with the help of the Möbius function. Using that result, bounds for non-unary alphabets, both in the DFA and in the NFA case, are proven.

Let's go into more detail. For a $k$-letter alphabet, define \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*} Note that $ g_k(n) = \sum_{i=1}^n f_k(i)$. We start with $f_1(k) $ and $g_1(k)$.

Enumeration of Unary DFA's

A unary DFA $M = (Q, \{a\},\delta, q_0,F) $ with states $q_0,\dots, q_{n-1}$ is minimal iff

  1. It is connected. Thus, after renaming, it the transition diagram consists of a loop and a tail, i.e. $\delta(q_i,a) = q_{i+1}$ and $\delta(q_{n-1},a)=q_j$ for some $j \leq n-1$.
  2. The loop is minimal.
  3. If $j \neq 0$, then either $q_{j-1} \in F $ and $q_{n-1} \notin F$ or $q_{j-1} \notin F $ and $q_{n-1} \in F$.

The loop $q_j,\dots, q_{n-1}$ is minimal iff the word $a_j \cdots a_{n-1}$ defined by \begin{equation*} a_i = \begin{cases} 1 \quad \text{if } q \in F, \\ 0 \quad \text{if } q \notin F \end{cases} \end{equation*} is primitive, which means it cannot be written in the form $x^k$ for some word $x$ and some integer $k \ge 2$.
The number $\psi_k(n)$ of primitive words of length $n$ over $k$-letter alphabets is known, see e.g. Lothaire,Combinatorics on Words. We have \begin{equation*} \psi_k(n) = \sum_{d | n} \mu(d) k^{n/d} \end{equation*} where $\mu(n)$ is the Möbius function. With the help of $ \psi_k(n) $ the paper proves exact formulas for $f_1(n)$ and $g_1(n)$ and shows that asymptotically (Theorem 5 and Corollary 6), \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*}

Enumeration of DFA's

The next step is a lower bound for $f_k(n)$. Theorem 7 states that \begin{equation*} f_k(n) \ge f_1(n) n^{ (k-1)n} \sim n 2^{n-1}n^{(k-1)n}. \end{equation*} For a set $\Delta \subset \Sigma$ of an automaton $M$, define $M_{\Delta}$ as the restriction of $M$ to $\Delta$.
The proof works by considering the set $S_{k,n}$ of DFA's $M$ over the $k$-letter alphabet $\{0,1,\dots,k-1 \}$ defined by

  1. Letting $M_{ \{0 \}}$ be one of the $f_1(n) $ different unary DFA's on $n$ states, and
  2. Choosing any $k-1$ functions $h_i : Q \to Q$ for $1 \le i < k$ and defining $\delta(q,i) = h_i(q)$ for $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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.