Optimal algorithm for counting the number of rows accepted by DFA

Question

Here is the question I met

Deterministic finite state machine (DFA) is a finite state machine that accepts / rejects finite strings of characters and performs only a unique calculation (or execution) of automation for each input string.

DFAs can be represented using state diagrams. For example, in the machine shown below, there are three states: S0, S1 and S2 (indicated graphically by circles). The automaton takes a finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading to the next state for 0 and 1. After reading the DFA symbol, it determinates from the state to another, following the transition arrow. For example, if the machine is currently in state S0, and the current input symbol is 1, then it deterministically goes into state S1. The DFA has an initial state (indicated graphically by an arrow going out of nowhere) where the calculations begin, and a set of acceptance states (indicated graphically by a double circle) that help determine when the calculation is successful.

These are some of the lines that DFA takes over,

0
00
000
11
110
1001

You are given a DFA input and an integer N. You must indicate how many different lines of length N a given DFA accepts.

Notes

• Assume that each state has two outgoing edges (one for 0 and one for 1). Both outgoing edges will not go into the same state.
• There may be several acceptance states, but only one onset state.
• The start state may also be an acceptance condition.

Input format

• States are numbered from 0 to K-1, where K is the total number of states in the DFA.
• You are given three arrays A, B, C and two integers D and N.
• Array A denotes edge 0 from state number i to state A [i], for all 0 ≤ i ≤ K-1
• Array B denotes 1 edge from state number i to state B [i], for all 0 ≤ i ≤ K-1
• Array C contains indices of all acceptance states.
• D .
• N , , N DFA.

1 ≤ K ≤ 50 
1 ≤ N ≤ 10^4

:

DFA, ,

A = [0, 2, 1]
B = [1, 0, 2]
C = [0]
D = 0

1

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

2

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

Mind, :

• . curr
• , N==0 curr , 1 ;
• 0 and 1 curr curr0 curr1. curr curr0 curr1, N-1;

, N, {0,1}. , 2^N, 1 <= N <= 10^4 .

, -? , NP-Complete, . .

Answer 1

. , N. , 0 1 , .

, / memoization. , , - . , , , . ( , .)

, , (State, Length) . .

= 0 . - , 1; , 0. K 1 N. K S. [S, K] [S0, K-1 ] + [S1, K-1], S0 - S, 0 S1 1.

, [StartState, N].

Answer 2

DP

public static int automata(ArrayList<Integer> a, ArrayList<Integer> b,
        ArrayList<Integer> c, int D, int n) {
    HashMap<Integer, Integer> map = new HashMap<>();
    int[][] table = new int[a.size()][n + 1];
    for (int i = 0; i < c.size(); i++) {
        map.put(c.get(i), 1);
    }
    for (int i = 0; i < a.size(); i++) {
        if (map.containsKey(i))
            table[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < a.size(); j++) {
            table[j][i] = table[a.get(j)][i - 1] + table[b.get(j)][i - 1];
        }
    }

    return table[D][n];
}