NFA到REGEX 将不确定的有限接受器转换为正则表达式。 介绍 非确定性有限接受器(NFA)是一种有限状态机,它读取字符串作为输入,并且可以接受或拒绝它。 与确定性有限接受器不同,NFA是不确定性的,这意味着在给定输入的情况下,机器有时可以选择其下一个状态。 下图给出了一个有限状态机的例子。 图1:不确定的有限受体示例 在上面的示例中,λ是一个空字符串,q_0是初始状态,也是最终状态。 边沿读数为1表示当输入中的下一个字符为1时机器将沿该边沿向下移动,而边沿标签“ 1,0”表示机器可沿1或0沿该边沿向下移动至下一个状态。如果读取最后一个字符后机器的状态为最终状态q_0,则接受输入字符串。 否则将被拒绝。 例如,如果输入是λ或10或1010,则机器很可能会接受输入。 使该图不确定的原因是沿着从q_0到q_2的边缘存在λ跃迁。 这意味着如果机器是q_0,则可以在空字符串上转到q_2。 另