我正在从 CLRS 学习字符串匹配与有限自动机。我正在解决一些练习题。对于练习题 32.3-1，
为模式 P = aabab 构造字符串匹配自动机，并说明它对文本字符串 T = aaababaabaababaab 的操作。
以下是我的过渡功能，
states a b
0 1 0
1 2 0
2 2 3
3 4 3
4 4 5
5 ? ?
我的转换功能正确吗？我如何填写最后一行？任何帮助
我假设您正在创建一个有限自动机，它接受包含模式的字符串aabab。
你的有限自动机有两个错误，
在状态3和状态 4 上，
对于状态3，如果输入是b，则必须返回状态0。例如，该模式aabb将迫使您返回 state 0。在这里，您必须从 state 重新开始0。
对于 state 4，如果输入是a，你必须回到 state2因为你有模式aa。例如，该模式aabaa将迫使您返回 state 2。
修正后的有限自动机如下所示，
states a b
0 1 0
1 2 0
2 2 3
3 4 0
4 2 5
5 5 5
这里 5 是你的接受状态。只有在字符串中找到所需的模式时，您才会达到此状态。一旦找到模式，无论字符串保持在接受状态。因此，对于输入a和b开启状态都5保持在5其自身上。
转换函数是 fa 接受带有子字符串 ' aabab ' 的字符串的函数。如果您要返回状态1fora和0for b，则转换函数接受以子字符串“ aabab ”结尾的字符串。鉴于只有状态 5 是接受状态。