regex - 将点星正则表达式转换为 NFA

Question

我正在将一组给定的正则表达式转换为一个 NFA，但我遇到了一些问题。我应该如何转换诸如“ab.*c”之类的正则表达式（表示匹配一个'a'、一个'b'、任意数量的字符，然后是一个'c'）？

我的最终目标是将单个 NFA 转换为 DFA（为此我使用了子集构造算法）。

Answer 1

正则表达式中的A.*对应于 NFA 中每个字母的循环状态。

该状态也将转换为c接受状态。

c在循环转换和接受转换两者中都可以，这就是为什么它是不确定的。