为用户构建给定语言的正则表达式。
正则表达式是用于描述语言并被有限自动机接受的语言。正则表达式是表示任何语言的最有效方式。设Σ是表示输入集的字母表。
Σ上的正则表达式可以定义如下-
Φ是一个正则表达式,表示空集。
ε是一个正则表达式,表示集合{ε},称为空串。
对于Σ中的每个'a','a'是一个正则表达式,表示集合{a}。
如果r和s表示语言的正则表达式。
L1和l2分别然后,
r+s等价于L1UL2union
rs等价于L1L2连接
r*等价于L1*闭包
r*被称为Kleen闭包或闭包,表示r无限次出现。
问题一
在集合l上写出接受a的所有组合的语言的正则表达式:={a}
解决方案
a的所有组合意味着a可以是零、单、双等。如果a出现零次,则表示空字符串。也就是说,我们期望集合{E,a,aa,aaa,....}。所以我们为此给出一个正则表达式如下-
R=a*
那是克林闭包了。
问题二
编写语言的正则表达式,在集合l上接受除空字符串之外的所有a组合:={a}
解决方案
必须为语言L={a,aa,aaa,....}构建正则表达式
这个集合表示没有空字符串。因此,我们可以将正则表达式表示如下-
R=a+
问题三
将语言L的正则表达式写在l:={O,l}上,使得所有字符串不包含子字符串01。
解决方案
语言如下-
L={E,0,1,00,11,10,100,.....}
上述语言的正则表达式如下-
R=(1*O*)
问题四
为包含字符串的语言编写正则表达式,其中每个0后紧跟11。
解决方案
常规期望将是:R=(011+1)*