6.正规语法和形式

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

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

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

L3={(ab)ⁿ|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={abⁿa|n≥0}

正规文法： 正规式：

S→aA B=ε+bB=b^*

A→Ba A=Ba=b^*a

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

L2={a^mbⁿ|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≥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