自动机的过渡状态图

Question

(a+b)*和(a.b)*的过渡状态图是什么？我对这两种状态图有点困惑。我发现他们俩都一样。

Answer 1

假设有颜色的状态是开始状态和接受状态。(a+b)*可以理解为“0或多个a's和b's的任意顺序。”(a.b)*可以理解为“零个或多个a's和b's的顺序。”注意，如果序列中断，节点3以死状态存在以拒绝匹配。

​

Answer 2

假设+表示合并和。意为级联：

(a+b)*
q   s   q'
--  --  --
q0  a   q0
q0  b   q0
(q0 is accepting)

(a.b)*
q   s   q'
--  --  --
q0  a   q1
q0  b   q2
q1  a   q2
q1  b   q0
q2  a   q2
q2  b   q2
(q0 is accepting; q2 is a dead state)

注意，(a+b)*描述a和b的所有字符串，因此我们只需要一种状态；没有字符串被拒绝。另一方面，a和b的字符串不匹配(a.b)*；我们以三种状态结束，因为：

1. 如果我们看到了"ab“的整数，我们就看不到任何"ab”或另一个整数“ab”(对应于状态q0)。
2. 如果我们看到"ab“后面跟着"a”的整数，那么我们可以看到a "b“和整数ab(对应于状态q1)。
3. 如果我们看到了除了在第1点和第2点中讨论的内容之外，没有什么可以添加到字符串中以获得“ab”的整数；我们已经搞砸了，任何带有这个前缀的字符串都不是在语言中(对应于“死”状态q2)。