Closure property is a helping technique to know the class of the resulting language when we do an operation on two languages of the same class. That is, suppose $L_1$ and $L_2$ belong to CFL and if CFL is closed under operation $\cup$, then $L_1 \cup L_2$ will be a CFL. But if CFL is not closed under $\cap$, that doesn’t mean $L_1 \cap L_2$ won’t be a CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed under an operation, we cannot say anything about the class of the resulting language of the operation – it may or may not belong to the class of the operand languages. In short, closure property is applicable, only when a language is closed under an operation.

Now, while applying closure property do remember the language hierarchy.

Regular $\subset$ DCFL $\subset$CFL $\subset$ REC $\subset$ RE.

So, if CFL is closed under Union, and $L_1$ and $L_2$ belong to CFL, then $L_1\cup L_2$ will be a CFL. But $L_1 \cup L_2$ can also be a regular language, which closure property can’t tell. For this we need to see $L_1$ and $L_2$.

**Heads Up!** Please don’t learn this table by heart . This is just to check your understanding and some of them are not required for GATE

Closure properties of language families

Operation | Regular | DCFL | CFL | CSL | Recursive | RE |
---|---|---|---|---|---|---|

Union | yes | no | yes | yes | yes | yes |

Intersection | yes | no | no | yes | yes | yes |

Complement | yes | yes | no | yes | yes | no |

Concatenation | yes | no | yes | yes | yes | yes |

Kleene star | yes | no | yes | yes | yes | yes |

Homomorphism | yes | no | yes | no | no | yes |

$\epsilon$-free Homomorphism | yes | no | yes | yes | yes | yes |

Substitution ($\epsilon$-free) | yes | no | yes | yes | no | yes |

Inverse Homomorphism | yes | yes | yes | yes | yes | yes |

Reverse | yes | no | yes | yes | yes | yes |

Intersection with a regular language | yes | yes | yes | yes | yes | yes |

14,727 total views, 16 views today