解释 TOC 中正则语言的不同操作。
语言是来自某个字母表(有限或无限)的一组字符串。换句话说,E*的任何子集L都是TOC中的一种语言。
一些特殊语言如下-
{}空集/语言,不包含字符串。
{s}一种包含一个字符串的语言,即空字符串。
例子
E={0,1}
L={x|x在E*中并且x包含偶数个0}
E={0,1,2,.,9,.}
L={x|x在E*中并且x形成一个有限长度的实数}
={0,1.5,9.326,.}
E={a,b,c,.,z,A,B,.,Z}
L={x|x在E*中,x是Pascal保留字}
={开始,结束,如果,...}
E={Pascal保留字}U{(,),.,:,;,...}U{LegalPascalidentifiers}
L={x|x在E*中,x是语法正确的Pascal程序}
E={英文单词}
L={x|x在E*中,x是语法正确的英语句子}
对正则语言的操作
对常规语言的一些操作如下-
联盟
路口
区别
级联
克莱恩*关闭
让我们一一了解这些操作。
联盟
如果Ll和IfL2是两种正则语言,它们的并集LluL2也将是正则的。
例如,Ll={anIn>O}和L2={bnIn>O}
L3=LlUL2={anUbnIn>O}也是正则的。
路口
如果Ll和IfL2是两种正则语言,它们的交集LlnL2也将是正则的。
例如,
Ll={ambnIn>0andm>O}和
L2={ambnUbnamIn>0andm>O}
L3=LlnL2={ambnIn>0andm>O}也是规则的。
级联
如果L1和IfL2是两种常规语言,则它们的串联L1.L2也将是常规的。
例如,
Ll={anIn>0}和L2={bnIn>O}
L3=L1.L2={am.bnIm>0和n>O}也是规则的。
Kleene闭包
如果Ll是正则语言,则其Kleene闭包Ll*也将是正则的。
例如,Ll=(aUb),Ll*=(aUb)*
补充
如果L(G)是正则语言,它的补L'(G)也将是正则的。可以通过L(G)从所有可能的字符串中减去包含的字符串来找到语言的补码。
例如,
L(G)={anIn>3}
L'(G)={anIn<=3}
注意:如果两个正则表达式生成的语言相同,则它们是等价的。例如,(a+b*)*和(a+b)*生成相同的语言。每个由(a+b*)*生成的字符串也由(a+b)*生成,反之亦然。
示例1
在集合l上写出接受a的所有组合的语言的正则表达式:={a}
a的所有组合均值a可以是零、单、双等。如果a出现零次,则表示空字符串。也就是说,我们期望集合{E,a,aa,aaa,....}。
所以我们为此给出一个正则表达式如下-
R=a*
那是克林闭包了。