Optimal algorithm to count the number of strings a DFA accepts

dfa with at least one a and exactly two b
dfa for at most 2 a
dfa for equal number of as and b's
give a dfa for σ 0 1 and strings that have an odd number of 1's and any number of 0's
w contains at least two 0s and at most one 1
dfa for odd length string
dfa examples
dfa for even length string

Here is the question I came across

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.

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.

These are some strings above DFA accepts,

0
00
000
11
110
1001

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.

Notes

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

Constraints

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

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.
My Solution

I have a brute force recursive solution in Mind which works like this:

  1. Start with the start state. let it be curr
  2. check if N==0 and curr is accept state then increment 1 to the total states and return;
  3. Now for both 0 and 1 as input let the curr state goes to curr0 and curr1. call the recursive function twice with curr state as curr0 and curr1 and also with N-1;
Problem with my solution

But the problem is that this solution will check all possible strings of length N containing {0,1}. So the Time complexity of this would be 2^N and since 1 <= N <= 10^4 this is exponential and not feasible.

Question

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.

The ideas in your solution are fine. The problem is that it can make MANY recursive calls on exactly the same state and N. You can see a simple example of this if both 0 and 1 take the start state to the same new state, where it will make an identical call on the new state twice.

This property is the hallmark of an algorithm that can be improved using dynamic programming and/or memoization. Depending on who you talk to, the two techniques are either the same thing or close cousins. Either way, they both make sure that the work for any given call is done only once, even if an identical call comes up later. (The identical call can just produce the same answer the original call did.)

To do this, we need to track which calls have been make, that is which combinations of (State, Length) have been computed. We can keep these answers in a table.

First initialize all the Length=0 spots in the table. If the state is an accept state, fill the spot with 1; if the state is not an accept state, fill the spot with 0. Now loop for K from 1 to N. For each K, loop over all states S. Fill in Table[S,K] with Table[S0,K-1] + Table[S1,K-1], where S0 is the state S transitions to on an input of 0 and S1 on an input of 1.

Finally, read off the answer from Table[StartState,N].

DFA of a string with at least two 0's and at least two 1's , The first thing that come to mind after reading this question us that we count the number of 1's and 0's. Thereafter if they both are at least 2 the string is accepted� 5 Algorithm to find the length of longest suffix between a String and a prefix of the String Oct 7 '15 5 Optimal algorithm to count the number of strings a DFA accepts Oct 10 '15 5 getAllNetworkInfo() is Deprecated Oct 20 '15

DP solution

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];
}

DFA for Strings not ending with "THE", Problem – Accept Strings that not ending with substring “THE”. Whenever any transition takes place, it will update the value of DFA with the number associated with In this way, apply this algorithm on entire string and if in the end, then reach For each lowercase English alphabet find the count of strings having these� Optimal algorithm to count the number of strings accepted by a DFA Here is the question I came across 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.

Just a small modification, this can be solved in O(n) space because state at time n only depends on time n-1. Here's the code:

int main()
{
    int k;
    cin >> k;
    vector<int> A(k);
    vector<int> B(k);
    vector<int> C;

    int val;

    for(int i = 0; i < k; ++i) cin >> A[i];
    for(int i = 0; i < k; ++i) cin >> B[i];
    for(int i = 0; i < k; ++i) 
    {
        cin >> val;
        if(val) C.push_back(i);
    }

    int D,N;
    cin >> D >> N;


    //For memoize
    // vector<vector<int>> dp(k, vector<int>(k,-1));


    // cout << rec(N, D, A, B, accepting_states) << endl;
    // cout << memoize(N, D, A, B, accepting_states, dp) << endl;

    vector<int> before(k, 0);
    vector<int> after(k);

    for(int ele:C) before[ele] = 1;

    for(int t = 1; t <= N; ++t)
    {
        for(int s = 0; s < k; ++s)
        {
            after[s] = before[A[s]] + before[B[s]];
        }
        before = after;
    } 

    cout << after[D] << endl;


}

Counting words accepted by a regular grammar, I suspect the best thing to do is just convert to a DFA and then apply the matrix powering algorithm. Let me mention one obvious approach that doesn't work: convert the NFA to a DFA (which will also be acyclic), then count the number of accepting paths in the DFA. This doesn't result in a polynomial-time algorithm, since the conversion can cause an exponential blowup in the size of the DFA.

Deterministic finite automaton, In the theory of computation, a branch of theoretical computer science, a deterministic finite The automaton takes a finite sequence of 0s and 1s as input . For each operation, an optimal construction with respect to the number of states whether a DFA accepts any strings (Emptiness Problem); whether a DFA accepts all� Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s. Examples: Input: N = 2 Output: 3 // The 3 strings are 00, 01, 10 Input: N = 3 Output: 5 // The 5 strings are 000, 001, 010, 100, 101

Suffix Automaton, A suffix automaton for a given string s is a minimal DFA (deterministic finite automaton / deterministic finite state machine) that accepts all the suffixes of the string s. The number of different substrings is the value d[t0]−1 (since we don't count the if (l > best) { best = l; bestpos = i; } } return t.substr(bestpos - best + 1, best); }� If the average number of pages is a non-integer, then it should be rounded to closest integer. In above example 2, average number of pages is (8 + 5 + 6 + 12)/3 = 31/3 which is rounded to 10. So the difference between average and number of pages on each day for the output shown above is “abs(8-10) + abs(5+6-10) + abs(12-10)” which is 5.

[PDF] A Counting Problem, other words, what is the cardinality of L(M) ∩ Σ n ? Our algorithm, then is just to compute f(p, i) for all p ∈ Q and 1 ≤ i ≤ n. Let's do a little example, answering how many strings of length n = 6 the following DFA M accepts:� DFA minimization is based on the notion of DFA equivalence: Two DFA's are called equivalent DFA's if and only if they accept the same strings of same set. A large number of computational problems

Comments
  • Can an outgoing edge "jump over" states (for example, S0 directly to S2)?
  • yeah it can go from any state to anyother
  • Hey thanks . I think this should work. I also thought about a dynamic programming algorithm but was mostly thinking in terms of if I can compute a matrix A[K][K] with length of paths between all pairs of states.