编译原理6 正规文法与正规式

 

---

1.分别写出描述以下语言的正规文法和正规式：

L1={abna|n≥0}。

L2={ambn|n≥1,m ≥1}

L3={（ab）n|n≥1}

 答：

正规文法：

L1：S->aA

　　A->bA | a

L2：S->aS

　    S->bS | ε

L3：S->aA

　　A->bS | b

正规式：

L1：ab*a

L2：aa*bb*

L3：ab(ab)*

 

 2.将以下正规文法转换到正规式

Z→0A
A→0A|0B
B→1A|ε

 答：Z=0A，A=0A+0B，B=1A+ε

　　A = 0A + OB

　　= 0A + 0(1A+ε)

　　= 0A + 01A + 0

　　=(0+01)A+0

　　= (0|01)*0

　　=(0101)A10

　　所以Z = 0A = 0 (0|01)*0

Z→U0|V1
U→Z1|1
V→Z0|0

答： 

Z = U0 + V1

　　U = Z1 + 1

　　V = Z0 + 0 

　　Z = (Z1+1)0 + V1

　　Z = (Z1+1)0 +(Z0+0)1

　　Z = Z10 + 10 +Z01 + 01

　　Z = Z(10+01)+10+01

　　Z = (10+01)*1001

S→aA
A→bA|aB|b
B→aA

 答:

　　S = aA , A = bA + aB + b , B = aA

　　A = bA + aB + b

　       = bA + aaA + b

　　   = (b+aa)A + b = (b|aa)*b

 　  S = aA = a(b|aa)*

 

I→l|Il|Id

答：　

 　　I→l | Il | Id

　　　　=l | I( I + d )

　　　　= I( I + d ) +I

　　　　 →Ia | b

　　　　得： a =( I + d ) ,b= I

 　　I=I( I + d ) *  =I( I | d ) *.