Java中的NFA模拟

2011-11-29 20 views 7 likes

我已经被赋予了模拟Java中的NFA的任务。现在我必须模拟NFA的以下正则表达式是Java中的NFA模拟

ab*((b|d)|c*)

我想我有太多的电子符号。我只是想知道下面的图片是否正确。

NFA

2011-11-29 unleashed

节点10,11,12和13可能会被压缩成两个节点？ –

这就是我最初的想法，但演讲者希望这种风格能够重复使用并使用汤普森建构来创建NFA。我只是怀疑2到3 e的过渡，3到4 e的过渡和4到5或4到7 e的过渡。 – unleashed

那么，2-3可以减少，在'b *'的情况下导致没有'b's，你会有一个从'1-2'转换的'e'。除此之外，我认为其余部分似乎是合适的。最终的结果是一样的，只有一个节点。 –

回答

你NFA图形是正确的。它将匹配正则表达式ab*((b|d)|c*)而没有别的。然而，它可能更简单，例如像这样：

enter image description here

2011-11-30 07:55:05

我不认为这是完全正确的，分支部分'（（b | d）| c *）'是两个分支，而不是三个，它是（b | d）或c *节点将它表示为一个完全独立的路径，然后分支到'b'或'd'中是否更准确？ –

我敢肯定，上面的一个不使用汤普森建设。它比较短，但我的演讲者给了我一种如何去做的风格。 – unleashed

@unleashed我会说汤普森是一种创建NFA的算法（一种程序），而不是一种NFA。你可以看到我的NFA是由汤普森创建的，然后进行了优化。（bw：问题是你的NFA是否等同于你的正则表达式，Thomspon没有:-)） –