What is Closure Properties

Closure property refers to some operation on language which returns the language with the same type in the result. If a language satisfies the condition for some operation, we can say that the language is closed under that operation.

We will discuss the closure properties of the following formal languages:

  • Regular Language (REG)
  • Deterministic Context Free Language (DCFL)
  • Context Free Language (CFL)
  • Context Sensitive Language (CSL)
  • Recursive Language (REC)
  • Recursive Enumerable Language (REL)

Closure Properties Table

Operation REG DCFL CFL CSL REC REL
Union YES NO YES YES YES YES
Concatenation YES NO YES YES YES YES
Kleen Closure YES NO YES YES YES YES
Reversal YES NO YES YES YES YES
Intersection YES NO NO YES YES YES
Complement YES YES NO YES YES NO
Inverse Homomorphism YES YES YES YES YES YES
Homomorphism YES NO YES YES YES YES
Substitution YES NO YES YES YES YES
Subset NO NO NO NO NO NO
Infinite - Union NO NO NO NO NO NO
Infinite - Intersection NO NO NO NO NO NO
Infinite - Difference NO NO NO NO NO NO
Prefix YES YES YES YES YES YES
Quotient YES NO YES YES YES YES
Cycle YES NO YES YES YES YES
Min YES NO NO      
Max YES NO NO      
Half YES NO NO      

Closure Properties with Regular Languages

Operation L = REG L = DCFL L = CFL L = CSL L = REC L = REL
L ∪ REG YES YES YES YES YES YES
L ∩ REG YES YES YES YES YES YES
L - REG YES YES YES YES YES YES
REG - L YES YES NO YES YES NO
L / REG YES YES YES YES YES YES
Closure Properties