regex - 构造对应于正则表达式的有限状态自动机。我的解决方案正确吗？

Question

我已经在油漆中画出了我的答案，它们正确吗？

(4c) 为字母表 {0, 1} 构造有限状态自动机，对应于下列每个正则表达式：

(一) 0

(ii) 1 | 0

(iii) 0 * (1 | 0)

Answer 1

前两个是正确的，尽管第一个可能可以写成（取决于您的约定）

(0) -- 0 --> ((1))

最后一个也是正确的，但可以简化为（无论何时ε出现，都可能有一种方法将边缘和状态压缩在一起以将其删除）

  +- 0 -+
  |     |
  v     |
 (0) ---+
 / \ 
1   0
 \ / 
  v
((1))

（请原谅我的 ascii 图。我(..)用于每个状态和((..))最终状态。）

请注意，这0*基本上是一个从状态到自身的循环，因为在读取0剩余的正则表达式以匹配之后是相同的（只要我们不在字符串的末尾）。