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 |
