计算 DFA 接受的字符串数的最佳算法

Question

这是我遇到的问题

确定性有限自动机 (DFA) 是一种有限状态机，它 accepts/rejects 个有限的符号字符串，并且只为每个输入字符串生成唯一的自动化计算（或运行）。

DFA 可以使用状态图表示。例如，在下面显示的自动机中，存在三种状态：S0、S1 和 S2（用圆圈表示）。自动机将有限的 0 和 1 序列作为输入。对于每个状态，0 和 1 都有一个指向下一个状态的转换箭头。读取符号后，DFA 会按照转换箭头确定性地从一个状态跳到另一个状态。例如，如果自动机当前处于状态 S0 且当前输入符号为 1，则它确定性地跳转到状态 S1。 DFA 有一个开始状态（用一个不知从哪里来的箭头图形表示）和一组接受状态（用双圆图形表示），这有助于定义计算何时成功。

这些是 DFA 接受以上的一些字符串，

给定一个 DFA 输入和一个整数 N。您必须说出给定 DFA 接受多少个长度为 N 的不同字符串。

注释

假设每个状态都有两条出边（一条代表0，一条代表1）。两条出边不会进入相同的状态。
可以有多个接受状态，但只有一个开始状态。
开始状态也可以是接受状态。

输入格式

状态从 0 到 K-1 编号，其中 K 是 DFA 中的状态总数。
给定三个数组 A、B、C 和两个整数 D 和 N。
数组A表示从状态编号i到状态A[i]的0边，对于所有0≤i≤K-1
数组B表示从状态编号i到状态B[i]的1条边，对于所有0≤i≤K-1
数组 C 包含所有接受状态的索引。
整数D表示起始状态。
整数 N 表示您必须计算给定 DFA 接受多少个长度为 N 的不同字符串。

约束

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 增加到总状态和 return;
现在，对于 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 都将开始状态带到相同的新状态，它将对新状态两次。

这属性是可以使用动态编程 and/or 记忆化改进的算法的标志。根据您与谁交谈，这两种技术要么是同一件事，要么是近亲。无论哪种方式，他们都确保任何给定调用的工作只完成一次，即使稍后出现相同的调用也是如此。（相同的调用只能产生与原始调用相同的答案。）

为此，我们需要跟踪进行了哪些调用，即计算了哪些 (State, Length) 组合。我们可以将这些答案保存在 table.

中

首先初始化table中所有Length=0的点。如果状态是接受状态，则用 1 填充该位置；如果状态不是接受状态，则用 0 填充该点。现在从 1 到 N 循环 K。对于每个 K，循环遍历所有状态 S。用 Table[S,K] 填充 [=23] =][S0,K-1] + Table[S1,K-1]，其中 S0 是 S 在输入 0 时转换到的状态，S1 在输入 1 时转换到的状态。

最后，从Table[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];
}

Answer 3

只是一个小修改，这可以在 O(n) space 中解决，因为时间 n 的状态仅取决于时间 n-1。这是代码：

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;


}

计算 DFA 接受的字符串数的最佳算法

Optimal algorithm to count the number of strings a DFA accepts

algorithm

np-complete

data-structures

输入 1

输入 2

我的解决方案

我的解决方案有问题

问题