正规式也称正则表达式,也是表示正现集的工具 对于字母表∑,Σ上的正规式和它所表示的正现集是递归定义 的: 1.ε和φ是Σ上的正规式,它们所表示的正规集分别为{e}和q 2.任何a∈Σ,a是Σ上的一个正规式,它所表示的正规集为 3.假定e1和e2都是∑上的正规式,它们所表示的正现集分别 为L(e1)和L(e2),那么,(e1)、el|e2、e1e2和e1*也都是正规式, 它们所表示的正规集分别为L(e1),L(e)uL(e2),L(e)L(e2)和L (e1) 由有限次使用上述三步骤而定义而构成的表达式就是∑上的 正规式,由这些正规式所表示的字符串集就是∑上的正规集
正规式也称正则表达式，也是表示正现集的工具。 对于字母表Σ，Σ上的正规式和它所表示的正现集是递归定义 的： 1．ε和φ是Σ上的正规式，它们所表示的正规集分别为{ε}和φ； 2．任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为 {a}； 3．假定e1和e2都是Σ上的正规式，它们所表示的正现集分别 为L(e1 )和L(e2 )，那么，(e1 )、e1 |e2、e1·e2和e1 *也都是正规式， 它们所表示的正规集分别为L(e1 )，L(e1 )∪L(e2 )，L(e1 )L(e2 )和L （e1）* 由有限次使用上述三步骤而定义而构成的表达式就是Σ上的 正规式，由这些正规式所表示的字符串集就是Σ上的正规集
例:令∑={a,b},则 ba*a(a|b)*(ab)y(abb)(a|b)*都是正规式,它们的正规 集为: ba"n≥0} 以a为首的字 含有两个相继的a或两个相继的b的字} 例:设21={0,1},则(01)(01)*是Σ1上的正规式 设∑2={A,B,0,1},则(AB)(A|B|01)*是∑2上的正 规式 定义3.1若两个正规式e1和e2所表示的正规集相同,则说e1和 e2是等价,记作e1=e2 例: ab=ba b(ab)*=(ba*b,(ab*=(a b")
例：令Σ={a,b}，则 ba* a(a|b)* (a|b)*(aa|bb)(a|b)*都是正规式，它们的正规 集为： {ban |n≥0} {以a为首的字} {含有两个相继的a或两个相继的b的字} 例：设Σ1={0，1}，则（0|1）（0|1）* 是Σ1上的正规式 设Σ2={A，B，0，1}*，则（A|B）（A|B|0|1）*是Σ2上的正 规式 定义 3.1若两个正规式e1和e2所表示的正规集相同，则说e1和 e2是等价，记作e1=e2。 例： a|b=b|a b(ab)*=(ba)*b , (a|b)*=(a*|b*)*
设r,s,t为正规式,则: (1)r|s=s (2)r|(s|t)=(r|s)t (3)(rs)t=r(st) (4)『(S)=rsrt (rstrt st (5)Er=rE=r (6)(r)=r 下面以(1)为例,证明之 证::L(rl)=L(r)∪L(s)=L(s)∪L(r)=L(s) ∴rS=S 证毕
设r，s，t为正规式，则： （1）r|s=s|r （2）r|(s|t)=(r|s)|t （3）(rs)t=r(st) （4）r(s|t)=rs|rt (r|s)t=rt|st （5）εr=rε=r （6）(r*)*=r* 下面以（１）为例，证明之 证：∵L(r|s)= L(r) ∪L(s)= L(s) ∪L(r)= L(s|r) ∴ r|s=s|r 证毕
1.将Σ的一个正规式转换成文法G=(Vn,Vt,P,S),令其中 的V=Σ,确定产生式和Vn的元素用如下办法。 对任何正规式r,选择一个非终结符S生成产生式S→r,并将 S定为G的识别符号。 若x和y都是正规式,对形如A→X的产生式,重写:A→xB, B→y两产生式,其中B是新选择的非终结符,即B∈Vn。 对已转换的文法中的形如A→x^y的产生式,重写为 A→xBAy B→→XBB 其中B为一新非终结符。 或 A→xAA-y 对形如A→y的产生式,重写为: A→xAy 不断利用上述规则做变换,直到每个产生式最多含有一个终结 符为止
1．将Σ的一个正规式转换成文法G=（Vn , Vt，P，S），令其中 的Vt =Σ，确定产生式和Vn 的元素用如下办法。 对任何正规式r，选择一个非终结符S生成产生式S→r，并将 S定为G的识别符号。 若x和y都是正规式，对形如A→xy的产生式，重写:A→xB， B→y两产生式，其中B是新选择的非终结符，即B∈Vn 。 对已转换的文法中的形如 A→x*y的产生式，重写为 A→xB A→y B→xB B→y 其中B为一新非终结符。 或 A→xA A→y 对形如A→x|y的产生式，重写为； A→x A→y 不断利用上述规则做变换，直到每个产生式最多含有一个终结 符为止
例:将R=a(ad)*转换成相应的正规文法,令S是文法的开始 符号、首先形成S→a(a)*,然后形成S→aA和A→(ad)*.再 重写第二条产生式形成 s→aAA→(a|d)AA→E 即:S→aAA→aAA→dAA 严格来说,正规文法不含ε规则,故消去之。改为: s→>aAaA→ aaaaaa|d 2将正视文法转换成正规式。基本上是上述过程的逆过程,最 后只剩下一个开始符 号定义的产生式,并且该产生式的右部不含非终结符。其转换 规则下: (1)产生式A→xB,B→y 有正规式A=xy (2)产生式A→XAy 有正规式A=x*y (3)产生式A→x,A→y 有正规式A=xy
例：将 R=a(a|d)*转换成相应的正规文法，令 S是文法的开始 符号、首先形成S→a(a|d)*，然后形成 S→aA和 A→(a|d)*．再 重写第二条产生式形成: S→aA A→(a|d)A A→ε 即：S→aA A→aA A→dA A→ε 严格来说，正规文法不含ε规则，故消去之。改为： S→aA|a A→aA|dA|a|d 2.将正视文法转换成正规式。基本上是上述过程的逆过程，最 后只剩下一个开始符 号定义的产生式，并且该产生式的右部不含非终结符。其转换 规则下： (1)产生式 A→xB,B→y 有正规式 A=xy (2)产生式 A→xA|y 有正规式A=x*y (3)产生式 A→x, A→y 有正规式A=x|y