NFA 代表语言之星 (01 U 001 U 010)*

Question

此 pdf第 5 页的问题。

提供一个可识别该语言的 NFA (01 U 001 U 010)*

我认为这是错误的，因为对于开头的空字符串应该有一个额外的开始状态（接受）进入状态 1。这就是在 Sipser 中证明 star 下的闭包的方式。我是不是错过了什么？

我认为应该是这样的：

Answer 1

不，您正确理解了第一个模式中的星星，但 NFA 是正确的。

x*

表示模式

x

重复 0 次或多次。

状态1是开始状态。您知道它可以匹配空字符串，因为开始状态也是结束状态。您可以想到的另一种方式是，左侧的箭头表示存在一个隐式开始状态，该状态接受空字符串并转换到状态 1。

假设我正确记得我的课程：

• 左侧第一个箭头表示启动时进入状态1。
• 双圆圈表示状态1也是有效的结束状态。
• ε 表示空字符串。这是有限自动机不确定性的部分原因。例如，如果您处于状态 5，则没有一个正确的响应，并且单个字符串可能能够遍历多个状态列表。