2

例如：给定以下符号序列，

a b c b c d d d b c b c d d d d e

可以接受它的最简单的 DFA 是 17 个状态的链。

而下面的正则表达式可以推导出上面的序列：

a (b c)* (d)* (b c)* (d)* e

对应的最小 DFA 有 8 个状态。

此外，正则表达式的a ((b c)* (d)*)* e最小 DFA 更小，有 4 个状态。它可以接受示例序列。

在上面的例子中，我只考虑了*运算符；更一般地，算子|也可以考虑减小 DFA 的大小。

所以，一般的问题是：

给定一个符号序列，如何找到能够接受它的最小 DFA？

4

2 回答 2

2

简单的。具有一种状态的 DFA 总是可以做到这一点。那个状态是开始状态，接受状态，并且所有符号转换环回它。那个微不足道的 DFA 接受所有字符串 (∑*)，并且绝对是最小的 DFA。

于 2012-10-19T03:00:11.903 回答
2
  1. 正则表达式 -> NFA
  2. 然后是 NFA -> DFA
  3. 然后是 DFA -> 最小 DFA

网上有很多算法，你可以用谷歌搜索每一步。
您可以检查您的 DFA/NFA。
http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

于 2012-10-19T03:59:01.690 回答