Ullman (TOC) Edition 3 Exercise 3.2 Question 8 (Page No. 108)

Question

Give an algorithm that takes a DFA  $A$ and computes the number of strings of length $n$ $($for some given $n$ not related to the number of states of $A)$ accepted by $A.$Your algorithm should be polynomial in both $n$ and the number of states of $A.$

Answer 1

Let R(k)ijm be the number of paths from state i to state j of length m that go through no state numbered higher than k. We can compute these numbers, for all states i and j, and for m no greater than n, by induction on k.

Basis: R0ij1 is the number of arcs (or more precisely, arc labels) from state i to state j. R0ii0 = 1, and all other R0ijm's are 0.

Induction: R(k)ijm is the sum of R(k-1)ijm and the sum over all lists (p1,p2,...,pr) of positive integers that sum to m, of R(k-1)ikp1 * R(k-1)kkp2 *R(k-1)kkp3 *...* R(k-1)kkp(r-1) * R(k-1)kjpr. Note r must be at least 2.

The answer is the sum of R(k)1jn, where k is the number of states, 1 is the start state, and j is any accepting state.