You do not have permission to edit this page, for the following reason:

The action you have requested is limited to users in one of the groups: Users, Administrators.


You can view and copy the source of this page.

Return to Closure Property of Language Families.

Closure property is a helping to know what will be the resulting language when we do an operation on two languages of the same class. That is, suppose <math>L_1</math> and <math>L_2</math> belong to CFL and if CFL is closed under operation <math>\cup</math>, then <math>L_1 \cup L_2</math> will be CFL. But if CFL is not closed under <math>\cap</math>, that doesn't mean <math>L_1 \cap L_2</math> won't be 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 result of the operation, it may or may not belong to that class. In short, closure property is useful, only when a language is closed under an operation.

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

Regular <math>\subset</math> DCFL <math>\subset</math>CFL <math>\subset</math> REC <math>\subset</math> RE. 

So, if CFL is closed under Union, and <math>L_1</math> and <math>L_2</math> belong to CFL, then <math>L_1\cup L_2</math> will be CFL. But <math>L_1 \cupL_2</math> may also be regular, which closure property can't tell.

Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column).
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
e-free Homomorphism Yes No Yes Yes Yes Yes
Substitution 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







blog comments powered by Disqus