Deterministic Finite Automaton

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.



These are some strings above DFA accepts,


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. Return answer modulo 109+7.


  • Assume each state has two outgoing edges(one for 0 and one for 1). Both outgoing edges won’t go to the same state.
  • There could be multiple accept states, but only one start state.
  • A start state could also be an accept state.

Input format

  • States are numbered from 0 to K-1, where K is total number of states in DFA.
  • You are given three arrays A, B, C and two integers D and N.
  • Array A denotes a 0 edge from state numbered i to state A[i], for all 0 ≤ i ≤ K-1
  • Array B denotes a 1 edge from state numbered i to state B[i], for all 0 ≤ i ≤ K-1
  • Array C contains indices of all accept states.
  • Integer D denotes the start state.
  • Integer N denotes you have to count how many distinct strings of length N the given DFA accepts.

1 ≤ K ≤ 50
1 ≤ N ≤ 104

Example :

For the DFA shown in image, input is
A = [0, 2, 1]
B = [1, 0, 2]
C = [0]
D = 0

Input 1
N = 2
Strings '00' and '11' are only strings on length 2 which are accepted. So, answer is 2.

Input 2
N = 1
String '0' is the only string. Answer is 1.

Start solving Deterministic Finite Automaton on Interview Code Editor
  • Hints are not available for this problem


Click here to start solving coding interview questions