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

Question

这是我遇到的问题

确定性有限自动机（DFA）是一种有限状态机，它接受/拒绝符号的有限字符串，并且仅对每个输入字符串产生唯一的自动化计算（或运行）。

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

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

0
00
000
11
110
1001

您会在输入中获得一个DFA，并输入一个整数N。您必须知道给定DFA接受多少个长度为N的不同字符串。

笔记

• 假设每个状态都有两个输出边（一个为0，一个为1）。两个输出边缘都不会进入同一状态。
• 可能有多个接受状态，但只有一个开始状态。
• 起始状态也可以是接受状态。

输入格式

• 状态从0到K-1编号，其中K是DFA中的状态总数。
• 您将获得三个数组A，B，C和两个整数D和N。
• 数组A表示从状态i到状态A [i]的0个边沿，对于所有0？一世 ？K-1
• 数组B表示从状态i到状态B [i]的1条边，对于所有0？一世 ？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中有一个蛮力递归解决方案，其工作方式如下：

1. 从开始状态开始。随它去curr
2. 检查N==0和curr是接受状态，则增加1总的状态和回报;
3. 现在0 and 1作为输入，让curr状态进入curr0和curr1。用curr状态as curr0和curr1并且用with 两次调用递归函数N-1;

我的解决方案有问题

但问题是，这种解决方案将检查长度的所有可能的字符串N包含{0,1}。因此，它的时间复杂度是2^N并且因为1 <= N <= 10^4这是指数级的并且不可行。

题

有没有人可以建议的有效解决方案？可能是NP-Complete这个问题，这是唯一的解决方案。任何帮助，将不胜感激。

Answer 1

解决方案中的想法很好。问题在于，它可以对完全相同的状态和N进行多次递归调用。如果0和1都将开始状态转换为相同的新状态，则可以看到一个简单的示例，它将在相同的状态上进行相同的调用。新状态两次。

此属性是可以使用动态编程和/或记忆来改进的算法的标志。取决于您与谁交谈，这两种技术既可以是同一事物，也可以是近亲。无论哪种方式，它们都可以确保任何给定呼叫的工作仅完成一次，即使稍后出现相同的呼叫也是如此。（相同的呼叫只能产生与原始呼叫相同的答案。）

为此，我们需要跟踪进行了哪些调用，即已计算出（状态，长度）的哪些组合。我们可以将这些答案保存在表格中。

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

最后，从Table [StartState，N]中读出答案。