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|ε
正规式 ： A ->0A |0B =0A | 0( 1A | ε )=0A + 01A +0 =( 0 + 01)A +0 -> aA | b
即a =( 0 + 01) ,b= 0 .而该形式产生 a*b , 既有 A = ( 0 + 01)* 0，代入 Z 中有
Z = 0( 0 + 01)*0 = 0( 0 | 01)*0 。
Z→U0|V1
U→Z1|1
V→Z0|0
正规式 ： Z→U0|V1 = ( Z1 + 1 ) 0 + （Z0 + 0）1=Z10 + 10 +Z01 + 01 =Z (10 + 01) + (10 + 01) →Za |a
即a =(10 + 01) .而该形式产生 aa* , 既有 Z = (10 + 01)* = (10 | 01)* .
S→aA
A→bA|aB|b
B→aA
正规式 ： A→bA|aB|b =bA +a(aA) + b= bA +a2A +b =(b+a2)A + b → aA | b
即a = ( b + a2) ,b = b .而该形式产生 a*b , 既有 A = (b+a2) * b ，代入 Z 中有
Z = a (b+a2) * b = a ( b | a2) * b
I→l|Il|Id
正规式 ： I→l | Il | Id =l | I( I + d )= I( I + d ) +I →Ia | b
即a =( I + d ) ,b= I .而该形式产生 ba* , 既有 I=I( I + d ) * =I( I | d ) *.