是否可以使用有限的正则表达式来表达具有无限数量字符串的语言？
Is it possible to express a language with infinite number of strings using a finite regular expression?
我正在尝试了解如何为某些我认为属于 "Infinite" 的语法生成正则表达式。我有以下 Σ = {0,1} 我想到了以下三种情况，这是我给出的猜测。
- 所有以
0结尾并以11结尾的字符串的集合。我的正则表达式如下：0+ [1*] [0*] 1+ 1。但是，我知道这个表达式不会涵盖该集合中的所有现有字符串集合。
- 包含至少两个连续
1 的所有字符串的集合。我的正则表达式如下：1 1+ [0+] [1+] 1。与第一点相同的问题。
- 所有以
0 开头且没有连续两个 1 的字符串的集合。我的正则表达式如下：0+ 1 0+ 1 [0+]。与第一点和第二点相同的问题。
我的问题如下：是否有可能用有限的正则表达式来表达这些具有无限数量字符串的语言。如果是，具体如何？
谢谢。
是的，任何正则语言都可以被有限自动机识别，并且正则语言可以表达无限多的匹配字符串。处理您的三个示例：
0 (0|1)* 1 1(0|1)* 1 1 (0|1)*0+ (1 0+)+ 1?
我正在尝试了解如何为某些我认为属于 "Infinite" 的语法生成正则表达式。我有以下 Σ = {0,1} 我想到了以下三种情况，这是我给出的猜测。
- 所有以
0结尾并以11结尾的字符串的集合。我的正则表达式如下：0+ [1*] [0*] 1+ 1。但是，我知道这个表达式不会涵盖该集合中的所有现有字符串集合。 - 包含至少两个连续
1的所有字符串的集合。我的正则表达式如下：1 1+ [0+] [1+] 1。与第一点相同的问题。 - 所有以
0开头且没有连续两个1的字符串的集合。我的正则表达式如下：0+ 1 0+ 1 [0+]。与第一点和第二点相同的问题。
我的问题如下：是否有可能用有限的正则表达式来表达这些具有无限数量字符串的语言。如果是，具体如何？ 谢谢。
是的，任何正则语言都可以被有限自动机识别，并且正则语言可以表达无限多的匹配字符串。处理您的三个示例：
0 (0|1)* 1 1(0|1)* 1 1 (0|1)*0+ (1 0+)+ 1?