如何连接字母表中相邻的 Kleene 星号？

Question

我遇到过需要将正则表达式从语言 {1,0} 转换为 NFA 图的情况。在正则表达式中，我发现有两个带有 Kleene 星号的串联符号 1*0*。基本上这意味着该字符串有任意数量的 1，后跟任意数量的 0。

在转换为 NFA 时，我感到困惑主要是因为有两个事务指向第一个符号 (1*) 接受状态的外部：一个回到初始状态的 epsilon 事务（因为它有一个 Kleene star), 以及初始状态 0* 的 epsilon 交易。

我不确定 1) 我是否可以在转换为 NFA 时让两个交易离开相同的状态，如果可以，2) 如何简化此交易。

如有任何帮助，我们将不胜感激！

Answer 1

您绝对可以从同一状态进行多个 epsilon 转换。

使用https://en.wikipedia.org/wiki/Thompson%27s_construction,

s和t的连接：s的初始状态是新的初始状态，t的接受状态是新的接受状态。 s的接受状态成为t的初始状态。

s 的 Kleene 闭包：引入一个新的初始状态和一个新的接受状态。添加从初始状态到最终状态的 epsilon 转换。添加从新首字母到原始首字母的 epsilon 转换，从原始接受到新接受的 epsilon 转换，以及从原始接受到原始初始的 epsilon 转换。

因此，我们的表达式 1*0* 分为： 1* 与 0* 连接。

1 本身就是 q --1--> f。通过 Kleene 转换为 NFA 产量

/--------------e--------------\
|                             V
q --e--> q1 --1--> q1f --e--> f
          ^        |
          \---e----/

0* 的结构类似。要连接它们，从第一个开始接受状态，并将其定义为第二个的起始状态：

/---------------e-------------\  /-------------e---------------\
|                             V  |                             V
q --e--> q1a --1--> q1f --e--> q0 --e--> q0a --0--> q0f --e--> f
          ^          |                    ^          |
          \-----e----/                    \-----e----/

为了简化，您可以使用相应的转换算法将其转换为NFA或DFA。

如何连接字母表中相邻的 Kleene 星号？

How do I concatenate adjacent Kleene star symbols from an alphabet?

regex

computation

epsilon

non-deterministic

nfa