26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I presume you mean "number of accepting words of size $n$", or something like that ? else, what is the number of accepting words for $\Sigma^*$ $\endgroup$ – Suresh Venkat Sep 12 '11 at 17:52
38
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The perfect answer: obvious only once you've read it. $\endgroup$ – Charles Sep 12 '11 at 18:00
  • 1
    $\begingroup$ This approach has exponential worst-case runtime if you have input other than a DFA. Is this not an issue for you, @Charles? You seem to include regular expressions, NFA and grammars in you questions, and also ask for an efficient way. $\endgroup$ – Raphael Sep 25 '11 at 9:31
17
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I appreciate the historical note! $\endgroup$ – Charles Sep 12 '11 at 21:03
  • 1
    $\begingroup$ Er, this is actually a method that works really well (and is simple, once you get it) in many circumstances. For example, you can do CFGs in exactly the same way. $\endgroup$ – Raphael Sep 12 '11 at 21:33
  • 1
    $\begingroup$ I see, I misunderstood. In that case, if you want to read into this, I recommend Kuich (1970) which I found more accessible than the work of C&S. He also covers this in a book of his which I don't remember. $\endgroup$ – Raphael Sep 27 '11 at 18:27
  • 1
    $\begingroup$ Are you saying you can count words of length $n$ in a regular language in polynomial time and without constructing DFA? Asked about the complexity of this on MO: mathoverflow.net/questions/162186/… $\endgroup$ – joro Apr 2 '14 at 12:36
  • 1
    $\begingroup$ @joro In case of unambiguous grammars, I think that this is true, yes. $\endgroup$ – Raphael Apr 2 '14 at 13:38
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The post above assumes that the given length is in unary. If instead the length is in binary, the problem is PSPACE-hard. I say this based on the proof that deciding equivalence of two regular expressions is PSPACE-hard. In that reduction, one reg-ex was constructed to accept all strings, and the other to accept all strings that are not valid rejecting computation histories of PSPACE machine M on input w. Using that second regular expression and the length of a computation history of M on w as inputs to the problem in question makes this other problem PSPACE-hard too. $\endgroup$ – Mikhail Rudoy Dec 31 '16 at 1:24
3
$\begingroup$

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.

$\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.