regex - 无限语言的正则表达式

Question

我对正则表达式有点困惑。是否存在识别无限语言的正则表达式，或者是否所有正则表达式都识别有限语言？

Answer 1

绝对有可能构建识别无限种语言的正则表达式。例如，简单的正则表达式a*匹配无限语言

{ ε, a, aa, aaa, aaaa, ... }

星号运算符在正则表达式中必不可少，使它们能够识别无限组字符串。

确实所有有限语言都是正则的，但并非所有正则语言都是有限的(如上所示)。形式语言理论告诉我们，有很多语言是无限的而不是规则的(例如 {0ⁿ1ⁿ | n ≥ 0})，但是，所以您不能总是为任意无限语言编写正则表达式。

希望这对您有所帮助!