知识点总结：
| 1 | 正规文法产生式的形式为A→aB或则A→a |
| 2 | ‘|’为或等同于算数里的加，‘.’为连接等同于算数里的乘，‘*’为闭包等同于算数里的幂 |
| 3 | 标识符的正规式为‘l(l|d)*’,常整数的正规为‘dd*’ |
| 4 | 正规文法和正规式可以互相转换 |
| 5 |
三个重要的规则：A→xB B→y 正规式为A=xy A→xA|y 正规式为A=x*y A→x A→y 正规式为A=x|y |
1.分别写出描述以下语言的正规文法和正规式：
L1={abna|n≥0}
L2={ambn|n≥1,m ≥1}
L2={（ab）n|n≥1}
∵正规文法的每一个产生式的形式都是A→aB或者是A→a
①设文法G(S)={abna|n≥0}
∴S->aA
A->Ba
B->bn
B->bB|ε
正规式
ab*a
②设文法G(S)={ambn|n≥1,m ≥1}
∴S->AB
A->aA|a
B->bB|b
正规式
aa*bb*
③设文法G(S)={（ab）n|n≥1}
∴S->(A)A|(A)
A->(ab)
正规式
(ab)(ab)*
2.将以下正规文法转换到正规式
（1）Z→0A
A→0A|0B
B→1A|ε
①答：
由题可知：
A=0A+0(1A+ε)
A=0A+01A+0ε=0A+01A+0=(0+01)A+0
令x=(0+01),y=0,根据规则A→xA|y转换为正规式为A=x*y
∴A=x*y=(0+01)*0
Z=0(0+01)*0=0(0|01)*0
（2）Z→U0|V1
U→Z1|1
V→Z0|0
答：
∵V→Z0|0
∴V=00*
∵U→Z1|1
∴U=11*
∴Z=11*0+00*1=1(1*0+00*)=1(1*0|00*)
∴Z=1(1*0|00*)
（3）S→aA
A→bA|aB|b
B→aA
答：
由题可得：
A=bA+aaA+b=(b+aa)A+b
相当于A->xB|y，转换为规则式为A=x*y
∴A=(b+aa)*b
∵S->aA
∴S=a(b+aa)*b=a(b|aa)*b
（4）I→l|Il|Id
答:
I=l+Il+Id=I(l+d)+l
相当于I->Ix|y，转换为规则式为I=yx*
∴I=l(l+d)*=l(l|d)*
∴I=l(l|d)*