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

<p>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\}|$.</p>

<p>Clearly:</p>

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

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

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

<p><strong>Edit:</strong> 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$.</p>

CC BY-SA 3.0
2011-09-12T21:03:47.817Z
I appreciate the historical note!
Charles
CC BY-SA 3.0
2011-09-12T21:33:51.650Z
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.
Raphael
CC BY-SA 3.0
2011-09-26T20:34:29.273Z
No disagreement, I just appreciate the addition of the reference which makes it easier to attribute things.
Charles
CC BY-SA 3.0
2011-09-27T18:27:43.147Z
I see, I misunderstood. In that case, if you want to read into this, I recommend [Kuich (1970)](http://www.sciencedirect.com/science/article/pii/S0019995870901051) 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.
Raphael
CC BY-SA 3.0
2011-09-27T19:40:49.500Z
Thanks!  (I of course upvoted you the moment I first read the answer, which is excellent. Otherwise I'd upvote you now.)
Charles
CC BY-SA 3.0
2014-04-02T12:36:55.030Z
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:  http://mathoverflow.net/questions/162186/complexity-of-counting-words-of-given-length-in-regular-or-context-free-language
joro
CC BY-SA 3.0
2014-04-02T13:38:22.920Z
@joro In case of unambiguous grammars, I think that this is true, yes.
Raphael
CC BY-SA 3.0
2011-09-12T18:47:01.130Z
2011-09-25T09:28:27.907Z
2011-09-25T09:28:27.907Z
Raphael
<p>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.</p>

CC BY-SA 3.0
2016-12-31T01:24:44.843Z
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.
Mikhail Rudoy
CC BY-SA 3.0
2016-12-19T16:44:55.660Z
2016-12-19T16:44:55.660Z
Miklós István
<p>This is #P hard via counting solution to monotone DNF formula.</p>
<p>Let <span class="math-container">$\phi(x_1,...x_n)$</span> be monotone <a href="https://en.wikipedia.org/wiki/Disjunctive_normal_form" rel="nofollow noreferrer">DNF formula</a> on <span class="math-container">$n$</span> variables.</p>
<p>We are trying to find regular language <span class="math-container">$L$</span> over alphabet <span class="math-container">$\{0,1\}$</span>
with all words of length <span class="math-container">$n$</span> and the words in <span class="math-container">$L$</span> are in one
to one correspondence with the satisfying assignment of <span class="math-container">$\phi$</span>.</p>
<p>Variable <span class="math-container">$x_i$</span> in <span class="math-container">$\phi$</span> corresponds to <span class="math-container">$i$</span>-th element in a word
<span class="math-container">$\{0,1\}^n$</span>.</p>
<p>To satisfy clause <span class="math-container">$c^j$</span> in <span class="math-container">$\phi$</span>, we match the indexes of the variables
in <span class="math-container">$c^j$</span> in a regular expression <span class="math-container">$W$</span> and the rest of the variables can be
arbitrary.</p>
<p>More formally set the regular expression
<span class="math-container">$W^j[i]=1$</span> if <span class="math-container">$x_i \in c^j$</span>,
otherwise, set <span class="math-container">$W^j[i]=0 + 1$</span> where <span class="math-container">$+$</span> denotes union.</p>
<p>E.g. for the clause <span class="math-container">$(x_1 \land x_4)$</span> we set <span class="math-container">$W^1=1 \; 0+1 \;  0+1 \; 1$</span>.</p>
<p>Finally, set <span class="math-container">$L = W^1 + W^2 \cdots W^m$</span>.</p>
<p>So far, <span class="math-container">$L$</span> is defined by regex. Experimentally it appears
to have NFA with polynomial size in <span class="math-container">$n$</span> (the grammar is obviously small).</p>

CC BY-SA 4.0
2020-10-25T12:27:14.230Z
Excellent! We can convert the regular expression into an NFA of polynomial size, e.g. using the Glushkov construction or the Thompson construction. Any of the standard constructions will do this in polynomial time.
Hermann Gruber
CC BY-SA 4.0
2020-10-26T11:09:03.330Z
@HermannGruber Could there be islands of tractability more general than DFA?
joro
CC BY-SA 4.0
2020-10-24T15:19:00.413Z
2020-10-24T15:19:00.413Z
joro
<p>The following: <a href="https://www.researchgate.net/profile/Pierre_Mckenzie/publication/232641490_Nondeterministic_NC1_Computation/links/00b4951820f4ba4c7e000000.pdfhttp://archive.numdam.org/ARCHIVE/ITA/ITA_2001__35_3/ITA_2001__35_3_259_0/ITA_2001__35_3_259_0.pdf" rel="nofollow noreferrer">CMTV</a>, 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 <a href="http://archive.numdam.org/ARCHIVE/ITA/ITA_2001__35_3/ITA_2001__35_3_259_0/ITA_2001__35_3_259_0.pdf" rel="nofollow noreferrer">CDL</a>. Notice that the automaton is fixed in this setting and the input word is the only input.</p>

CC BY-SA 3.0
2016-12-30T13:20:00.823Z
2016-12-30T13:20:00.823Z
SamiD
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-09-12T18:00:07.503Z
The perfect answer: obvious only once you've read it.
Charles
CC BY-SA 3.0
2011-09-25T09:31:54.440Z
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.
Raphael
CC BY-SA 3.0
2011-09-12T17:56:16.170Z
2011-09-12T18:02:56.580Z
2011-09-12T18:02:56.580Z
David Eppstein
<p>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.</p>

<p><a href="http://www.cs.fsu.edu/~ackerman/" rel="noreferrer">Margareta Ackerman</a> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-09-12T17:52:55.347Z
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^*$
Suresh Venkat
<ds.algorithms><co.combinatorics><fl.formal-languages><regular-language>
Counting words accepted by a regular grammar
Charles
# Counting words accepted by a regular grammar

(Asked by: username_0 on 2011-09-12)

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](http://www.cs.fsu.edu/~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.

**Tags:** ds.algorithms, co.combinatorics, fl.formal-languages, regular-language
> **Comments:**
> **username_1**: 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^*$  

---

## 5 answers

### Answer by username_8 on 2011-09-12. Score: 39 | Accepted answer

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.

> **Comments:**
> **username_0**: The perfect answer: obvious only once you've read it.  
> **username_2**: 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.  

---

### Answer by username_2 on 2011-09-12. Score: 22

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

> **Comments:**
> **username_0**: I appreciate the historical note!  
> **username_2**: 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.  
> **username_0**: No disagreement, I just appreciate the addition of the reference which makes it easier to attribute things.  
> **username_2**: I see, I misunderstood. In that case, if you want to read into this, I recommend [Kuich (1970)](http://www.sciencedirect.com/science/article/pii/S0019995870901051) 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.  
> **username_0**: Thanks!  (I of course upvoted you the moment I first read the answer, which is excellent. Otherwise I'd upvote you now.)  
> **username_3**: 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:  http://mathoverflow.net/questions/162186/complexity-of-counting-words-of-given-length-in-regular-or-context-free-language  
> **username_2**: @joro In case of unambiguous grammars, I think that this is true, yes.  

---

### Answer by username_4 on 2016-12-19. Score: 9

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.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_3 on 2020-10-24. Score: 4

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

Let $\phi(x\_1,...x\_n)$ be monotone [DNF formula](https://en.wikipedia.org/wiki/Disjunctive_normal_form) 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).

> **Comments:**
> **username_6**: Excellent! We can convert the regular expression into an NFA of polynomial size, e.g. using the Glushkov construction or the Thompson construction. Any of the standard constructions will do this in polynomial time.  
> **username_3**: @HermannGruber Could there be islands of tractability more general than DFA?  

---

### Answer by username_7 on 2016-12-30. Score: 4

The following: [CMTV](https://www.researchgate.net/profile/Pierre_Mckenzie/publication/232641490_Nondeterministic_NC1_Computation/links/00b4951820f4ba4c7e000000.pdfhttp://archive.numdam.org/ARCHIVE/ITA/ITA_2001__35_3/ITA_2001__35_3_259_0/ITA_2001__35_3_259_0.pdf), 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](http://archive.numdam.org/ARCHIVE/ITA/ITA_2001__35_3/ITA_2001__35_3_259_0/ITA_2001__35_3_259_0.pdf). Notice that the automaton is fixed in this setting and the input word is the only input.


---

