Theorem: The family of regular languages is
closed under union, concatenation, iteration.
• Let L1, L2 be two regular languages
• Then, there exist two REs r1, r2:
L(r1) = L1, L(r2) = L2;
• By the definition of regular
expressions:
• r1.r2 is a RE denoting L1 L2
• r1 + r2 is a
RE denoting L1 È L2
• r1* is a RE
denoting L1*
• Every RE
denotes regular language, so