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

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

我最终的目标是将单个NFA转换为DFA（并且我正在使用子集构建算法）。

这需要更多的上下文。一旦你了解了算法（实际上即使你不知道），这种转换也是微不足道的，如果你不知道这一点，不清楚你想如何使用NFA，或者你会怎么理解一个答案，就此事。你的知识水平如何？ –

我不打算直接与NFA合作，因为我想与之合作的只是DFA。我正在将正则表达式转换为DFA（通过正则表达式 - > NFA - > DFA），但。*是一个我认为我处理不正确的情况，因为当我尝试使用交叉转换构建自动机时，空间炸毁（但不是当我试图在没有交叉转换的情况下构建它时）。 –

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

该状态也将有c过渡到接受状态。

在循环转换和接受转换中都有c是完全可以的 - 这就是为什么它是非确定性的。

2012-05-23 14:18:51

回答