Closure Properties

• A set is closed under an operation if applying that operation to any members of the set always yields a member of the set.
• For example, the positive integers are closed under addition and multiplication, but not division.
• Various Closure Properties are as follows −
  • Union
  • Intersection
  • Concatenation
  • Kleene closure
  • Complement

Regular Sets

• Any set that represents the value of the Regular Expression is called a Regular Set.
• A language or set is called Regular if it is accepted by a Finite-State Automaton.
• In an automata theory, there are different Closure Properties for Regular Languages or Sets.
• Let A and B be languages (remember they are sets).

• Concatenation operation can be defined for these two regular sets as follows:

  AB = {wv : w ∈ A and v ∈ B}

Theorem -

The class of regular languages or sets is closed under union, intersection, complementation, concatenation, and kleene closure.

Here, we see the Concatenation Property of two Regular Sets.

The Regular Sets are Closed under Concatenation

Proof -

Prove for arbitrary Regular Sets or Languages $L1$ and $L2$ that $L1.L2$ is a regular language.

– Let $E1$ and $E2$ be REGEX accepting $L1$ and $L2$.

– REGEX Construction:

We claim the REGEX

$$E = E1.E2$$

accepts $L1.L2,$ i.e. $L(E1.E2) = L(E1).L(E2)$

– Proof of correctness: Trivial by definition of Regular Expressions.

– $L1.L2$ is regular since there is a REGEX $E1.E2$ accepting this language.

Examples -

1]

E1 = (0+1)*0

E2 = 01(0+1)*

Where,

L1 = {0, 00, 10, 000, 010, ......} (Set of strings ending in 0)

and L2 = {01, 010,011,.....} (Set of strings beginning with 01)

Therefore,

L1.L2 = {001,0010,0011,0001,00010,00011,1001,10010,.............}

Set of strings containing 001 as a substring which can be represented by an

$E − (0 + 1)^*001(0 + 1)^*$

Hence, proved.

2]

L1 = {an | n > 0} and L2 = {bn | n > O}

L3 = L1.L2 = {am . bn | m > 0 and n > O}

Hence, proved.

A Regular Set has an FA or an RE. Regular Sets or Languages are closed under Union, Concatenation, Intersection, Complementation, and Kleene Closure.