第六次作业 正规文法与正规式

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

①L1={abⁿa|n≥0}。

②L2={a^mbⁿ|n≥1,m ≥1}

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

 解：正规文法：                                              正规式：

①S→aA ，A→bⁿa ，                                   ①B=bB|ε=b*

A→Ba ，B →bⁿ ，                                           A=Ba=b*a

B→bB|ε                                                            S=aA=ab*a

②S→AB ， A→a^{m                                              ②B=bB|b=b*b}

A→aA|a , B→b^{n                                                      A=aA|a=a*a}

B→bB|b　　　　　　　　　　　　　　　　S=AB=aa*b*b

③S→（A）A|（A）                                       ③A=ab

A→（ab）                                                          S=（A）A|（A）=（ab）（ab）*

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

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

 解：A=0A|0B ， B=1A|ε  => A=0A+0(1A+ε)  => A =0A+01A+0=(0+01)A+0=(0+01)*0

Z=0A=0(0+01)*0

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

 解：U=Z1|1 ， V=Z0|0 => U=Z1+1 ， V=Z0+0 

Z=U0|V1  =>  Z=U0+V1 => Z=(Z1+1)0+(Z0+0 )1 => Z =Z10+10+Z01+01=Z(10+01)+(10+01)=(10|01)*(10|01)

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

 解：A=bA|aB|b ， B=aA => A=bA+a(aA)+b=bA+aaA+b=(b+aa)A+b=(b|aa)*b

       S=aA=a(b|aa)*b

④I→l|Il|Id

解：I=l|Il|Id => I=I+II+Id=l+I(l+d)==l(l+d)*=l(l|d)*