内容说明介绍8closure properties of regular languages min.pdfVIP

ClosurePropertiesofRegular

Languages

Union,Intersection,Difference,

Concatenation,KleeneClosure,

Reversal,Homomorphism,Inverse

Homomorphism

1

ClosureUnderUnion

IfLandMareregularlanguages,sois

LM.

Proof:LetLandMbethelanguagesof

regularexpressionsRandS,

respectively.

ThenR+Sisaregularexpression

whoselanguageisLM.

2

ClosureUnderConcatenation

andKleeneClosure

Sameidea:

RSisaregularexpressionwhoselanguage

isLM.

R*isaregularexpressionwhoselanguage

isL*.

3

ClosureUnderIntersection

IfLandMareregularlanguages,then

soisLM.

Proof:LetAandBbeDFA’swhose

languagesareLandM,respectively.

ConstructC,theproductautomatonofA

andB.

MakethefinalstatesofCbethepairs

consistingoffinalstatesofbothAandB.

4

Example:ProductDFAfor

Intersection

00

10

AB[A,C][A,D]

0,1111

0

0

10[B,C][B,D]

1

0

CD

1