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

Question

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

Answer 1

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

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

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

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

希望这可以帮助！