Difference between revisions of "Closure Property of Language Families"

Revision as of 12:05, 26 February 2014

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 <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 a 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 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 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 a CFL. But <math>L_1 \cup L_2</math> can also be a regular language, which closure property can't tell. For this we need to see <math>L_1</math> and <math>L_2</math>.

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