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
=ab(1+S)
=ab(ab)*
———————————————————————————-
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+0(1A+ε) 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=0(0101)*0 =(10101)*(10101)
S→aA I→l|Il|Id
A→bA|aB|b
B→aA
正规式： 正规式：
A=bA+aB+b I=I+II+Id
=bA+a(aA)+b =I+I(I+d)
=(b+aa)A+b =I(I+d)*
=(b1aa)*b =III(d)*
S=aA=a(b1aa)*b