Closure properties of Regular languages

In an automata theory, there are different closure properties for regular languages. They are as follows −

• Union
• Intersection
• concatenation
• Kleene closure
• Complement

Let see one by one with an example

Union

If L1 and If L2 are two regular languages, their union L1 U L2 will also be regular.

Example

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

L3 = L1 U L2 = {an U bn | n > O} is also regular.

Intersection

If L1 and If L2 are two regular languages, their intersection L1 ∩ L2 will also be regular.

Example

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

L2= {am bn U bn am | n > 0 and m > O}

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

Concatenation

If L1 and If L2 are two regular languages, their concatenation L1.L2 will also be regular.

Example

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

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

Kleene Closure

If L1 is a regular language, its Kleene closure L1* will also be regular.

Example

L1 = (a U b )

L1* = (a U b)*

Complement

If L(G) is a regular language, its complement L'(G) will also be regular. Complement of a language can be found by subtracting strings which are in L(G) from all possible strings.

Example

L(G) = {an | n > 3} L'(G) = {an | n <= 3}

Note − Two regular expressions are equivalent, if languages generated by them are the same. For example, (a+b*)* and (a+b)* generate the same language. Every string which is generated by (a+b*)* is also generated by (a+b)* and vice versa.

Decision Properties:

Approximately all the properties are decidable in case of finite automaton.

(i) Emptiness 
(ii) Non-emptiness 
(iii) Finiteness 
(iv) Infiniteness 
(v) Membership 
(vi) Equality  

These are explained as following below.

(i) Emptiness and Non-emptiness:

• Step-1: select the state that cannot be reached from the initial states & delete them (remove unreachable states).
• Step 2: if the resulting machine contains at least one final states, so then the finite automata accepts the non-empty language.
• Step 3: if the resulting machine is free from final state, then finite automata accepts empty language.

  (ii) Finiteness and Infiniteness:

  • Step-1: select the state that cannot be reached from the initial state & delete them (remove unreachable states).
  • Step-2: select the state from which we cannot reach the final state & delete them (remove dead states).
  • Step-3: if the resulting machine contains loops or cycles then the finite automata accepts infinite language.
  • Step-4: if the resulting machine do not contain loops or cycles then the finite automata accepts infinite language.
  (iii) Membership:
  Membership is a property to verify an arbitrary string is accepted by a finite automaton or not i.e. it is a member of the language or not.

  Let M is a finite automata that accepts some strings over an alphabet, and let ‘w’ be any string defined over the alphabet, if there exist a transition path in M, which starts at initial state & ends in anyone of the final state, then string ‘w’ is a member of M, otherwise ‘w’ is not a member of M.

  (iv) Equality:
  Two finite state automata M1 & M2 is said to be equal if and only if, they accept the same language. Minimise the finite state automata and the minimal DFA will be unique.