title: Optimal algorithm to count the number of strings a DFA accepts
body: <p>Here is the question I came across</p>
  
  <p>Deterministic finite automaton(DFA) is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automation for each input string.</p>
  
  <p>DFAs can be represented using state diagrams. For example, in the automaton shown below, there are three states: S0, S1, and S2 (denoted graphically by circles). The automaton takes a finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading out to a next state for both 0 and 1. Upon reading a symbol, a DFA jumps deterministically from a state to another by following the transition arrow. For example, if the automaton is currently in state S0 and current input symbol is 1 then it deterministically jumps to state S1. A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accept states (denoted graphically by a double circle) which help define when a computation is successful.</p>
  
  <p><a href="https://i.stack.imgur.com/cNmcl.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cNmcl.png" alt="Sample DFA"></a>
  These are some strings above DFA accepts,</p>
  
  <pre><code>0
  00
  000
  11
  110
  1001
  </code></pre>
  
  <p>You are given a DFA in input and an integer N. You have to tell how many distinct strings of length N the given DFA accepts.</p>
  
  <p>Notes </p>
  
  <ul>
  <li>Assume each state has two outgoing edges(one for 0 and one for 1). Both outgoing edges won’t go to the same state.</li>
  <li>There could be multiple accept states, but only one start state.</li>
  <li>A start state could also be an accept state.</li>
  </ul>
  
  <p>Input format </p>
  
  <ul>
  <li>States are numbered from 0 to K-1, where K is total number of states in DFA.</li>
  <li>You are given three arrays A, B, C and two integers D and N.</li>
  <li>Array A denotes a 0 edge from state numbered i to state A[i], for all 0 ≤ i ≤ K-1</li>
  <li>Array B denotes a 1 edge from state numbered i to state B[i], for all 0 ≤ i ≤ K-1</li>
  <li>Array C contains indices of all accept states.</li>
  <li>Integer D denotes the start state.</li>
  <li>Integer N denotes you have to count how many distinct strings of length N the given DFA accepts.</li>
  </ul>
  
  <p>Constraints</p>
  
  <pre><code>1 ≤ K ≤ 50 
  1 ≤ N ≤ 10^4
  </code></pre>
  
  <p>Example :</p>
  
  <p>For the DFA shown in image, input is</p>
  
  <pre><code>A = [0, 2, 1]
  B = [1, 0, 2]
  C = [0]
  D = 0
  </code></pre>
  
  <h2>Input 1</h2>
  
  <pre><code>N = 2
  Strings '00' and '11' are only strings on length 2 which are accepted. So, answer is 2.
  </code></pre>
  
  <h2>Input 2</h2>
  
  <pre><code>N = 1
  String '0' is the only string. Answer is 1.
  </code></pre>
  
  <h2>My Solution</h2>
  
  <p>I have a brute force recursive solution in Mind which works like this:</p>
  
  <ol>
  <li>Start with the start state. let it be <code>curr</code></li>
  <li>check if <code>N==0</code> and <code>curr</code> is accept state then increment <code>1</code> to the total states and return;</li>
  <li>Now for both <code>0 and 1</code> as input let the <code>curr</code> state goes to <code>curr0</code> and <code>curr1</code>. call the recursive function twice with <code>curr</code> state as <code>curr0</code> and <code>curr1</code> and also with <code>N-1</code>; </li>
  </ol>
  
  <h2>Problem with my solution</h2>
  
  <p>But the problem is that this solution will check all possible strings of length <code>N</code> containing <code>{0,1}</code>. So the Time complexity of this would be <code>2^N</code> and since <code>1 &lt;= N &lt;= 10^4</code> this is exponential and not feasible.</p>
  
  <h2>Question</h2>
  
  <p>Is there an efficient solution to this problem that this that someone could suggest? May be this problem is NP-Complete and this is the only solution. Any help would be appreciated.</p>