无限语言的正则表达式

Question

我只是对正则表达式感到困惑.可以有一个识别无限语言的正则表达式,还是所有正则表达式都能识别有限语言？

Answer 1

绝对可以构建识别无限语言的正则表达式.例如,简单的正则表达式a*与无限语言匹配

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

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

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

希望这可以帮助!