0

我有这个正则表达式

[A-E]|[A-E]{3}|[A-E]{4} 

[A-E]|[A-E] [A-E] [A-E]|[A-E][A-E][A-E] [A-E]

它识别字符串A,B, ABC, BCD, BCDE, etc.

我想构建 NFA 但不知道我是否正确

  1. 我已经做到了 http://s1.postimg.org/627870q8v/image.png

  2. 或这个

http://s10.postimg.org/sqbxf2t5l/image.png

哪一个是正确的？

我的[A-E]NFA 是

http://s17.postimg.org/4b0q1w1mn/image.png

4

1 回答 1

1

最小 DFA 如下

0 -> 1 -> 2 -> 3 -> 4

每个过渡拱由 [AE] 签名且最终状态 = {1,3,4}

事实上，这个 DFA 与你的 NFA 是等价的。不过，我发现第二个更清楚。

于 2013-04-22T14:41:23.290 回答