Counting words accepted by a regular grammar

Question

Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of interest.

Margareta Ackerman has two papers on the related subject of enumerating words accepted by an NFA, but I wasn't able to modify them to count efficiently.

It seems like the restricted nature of regular languages should make counting them relatively easy -- I almost expect a formula more than an algorithm Unfortunately my searches so far haven't turned up anything, so I must be using the wrong terms.

Answer 1

For a DFA, in which the initial state is state $0$, the number of words of length $k$ that end up in state $i$ is $A^k[0,i]$, where $A$ is the transfer matrix of the DFA (a matrix in which the number in row $i$ and column $j$ is the number of different input symbols that cause a transition from state $i$ to state $j$). So you can count accepting words of length exactly $k$ easily, even when $k$ is moderately large, just by calculating a matrix power and adding the entries corresponding to accepting states.

The same thing works for accepting words of length at most $k$, with a slightly different matrix. Add an extra row and column of the matrix, with a one in the cell that's both in the row and the column, a one in the new row and the column of the initial state, and a zero in all the other cells. The effect of this change to the matrix is to add one more path to the initial state at each power.

This doesn't work for NFAs. I suspect the best thing to do is just convert to a DFA and then apply the matrix powering algorithm.

Answer 2

Let $A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$ be a (nondeterministic) finite automation with starting state $q_1$, $Q_F \subseteq Q$ and $\delta \subseteq Q\times\Sigma\times Q$.

Let $Q_i(z)$ the generating function for all the words that can be accepted starting in $q_i$, that is the $n$th coefficient of its series expansion $[z^n]Q_i = |\{w \mid |w| = n \wedge w \text{ accepted from } q_i\}|$.

Clearly:

$Q_i(z) = \left[ q_i \in Q_F \right] + \sum\limits_{(q_i, a, q_j) \in \delta} x \cdot Q_j(z)$

Solve the resulting (linear) equation system for $Q_1$ (using Mathematica or a similar tool). Then, $[z^n]Q_1$ is the desired quantity.

This goes back to a technique introduced for grammars by Chomsky and Schützenberger (1963); it easily transfers to finite automata.

Edit: If you want to account for $\varepsilon$-transitions, just leave out factor $x$ in the sum for the corresponding transition. Similiarly, if you have "compressed" edges, i.e. instead of symbol $a \in \Sigma$ a word $w \in \Sigma^k$ on a transition, replace $x$ with $x^k$.

Answer 3

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation of strings in regular languages. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 551–557, 1995.

Answer 4

The following: CMTV, considers the complexity class $\#\mathsf{NC}^1$ which is (essentially, but in somewhat more general setting) the class of functions counting the number of accepting computations of a nondeterministic finite automaton on an input word of a certain length. Many results are now known about this complexity class including containment in deterministic logspace as a consequence of CDL. Notice that the automaton is fixed in this setting and the input word is the only input.

Answer 5

This is #P hard via counting solution to monotone DNF formula.

Let $\phi(x_1,...x_n)$ be monotone DNF formula on $n$ variables.

We are trying to find regular language $L$ over alphabet $\{0,1\}$ with all words of length $n$ and the words in $L$ are in one to one correspondence with the satisfying assignment of $\phi$.

Variable $x_i$ in $\phi$ corresponds to $i$-th element in a word $\{0,1\}^n$.

To satisfy clause $c^j$ in $\phi$, we match the indexes of the variables in $c^j$ in a regular expression $W$ and the rest of the variables can be arbitrary.

More formally set the regular expression $W^j[i]=1$ if $x_i \in c^j$, otherwise, set $W^j[i]=0 + 1$ where $+$ denotes union.

E.g. for the clause $(x_1 \land x_4)$ we set $W^1=1 \; 0+1 \; 0+1 \; 1$.

Finally, set $L = W^1 + W^2 \cdots W^m$.

So far, $L$ is defined by regex. Experimentally it appears to have NFA with polynomial size in $n$ (the grammar is obviously small).