1.描述以下语言的正规文法和正规式：
L1={abna|n≥0}。
L2={ambn|n≥1,m ≥1}
L3={ab)n|n≥1}
2.将以下正规文法转换到正规式
Z→0A
A→0A|0B
B→1A|ε
Z→U0|V1
U→Z1|1
V→Z0|0
S→aA
A→bA|aB|b
B→aA
I→l|Il|Id
———————————————————————————-
1、
L1={abna|n≥0}
正规文法： 正规式：
S→aA B=ε+bB=b*
A→Ba A=Ba=b*a
B→bB|ε S=aA=ab*a
L2={ambn|n≥1,m ≥1}
正规文法： 正规式：
S→AB A=aA+a=a*a
A→aA|a B=bB+b=b*b
B→bB|b S=AB=aa*bb
L3={ab)n|n≥1}
正规文法： 正规式：
S→ab|abS S=ab+abS
=ab1+S)
=abab)*
———————————————————————————-
2、
Z→0A Z→U0|V1
A→0A|0B U→Z1|1
B→1A|ε V→Z0|0
正规式： 正规式：
A=0A|0B U=Z1+1
=0A+0B V=Z0+0
=0A+01A+ε) Z=00+V1
=0A+01A+0 =Z1+1)0+Z0+0)1
=0+01)A+0 =Z10+10+Z01+01
=0101)*0 =Z+1)10+01)
Z=0A=00101)*0 =10101)*10101)
S→aA I→l|Il|Id
A→bA|aB|b
B→aA
正规式： 正规式：
A=bA+aB+b I=I+II+Id
=bA+aaA)+b =I+II+d)
=b+aa)A+b =II+d)*
=b1aa)*b =IIId)*
S=aA=ab1aa)*b