regex - NFA 如何实现否定正则表达式

Question

我尝试使用 NFA 来实现否定正则表达式。

我知道 NFA 可以很容易地结合正则表达式ab a|b和a*

并且品种[ab]可以转换为a|b

但是如何转换[^ab]为 NFA 片段？

Answer 1

这只是一个字符类。NFA 的转换用单个字符或 lambda（空字符串）标记。要实现一个字符类，只需为类中的每个字符设置一个转换。否定类只是为每个不在该类中的字符实现一个转换。由于 NFA 需要有一个有限的字母表，所以这完全没有问题。如果 A 是字母表并且您想要 [^ab]，那么对于集合 A - {a, b} 中的每个字符都需要一个转换。