Closure Property of Language Families Revision as of 10:42, 26 February 2014 by Arjun Suresh (talk | contribs) (Created page with "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 L_1 and L_2 belong to CF...") (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 L_1 and L_2 belong to CFL and if CFL is closed under operation U, then L_1 U L_2 will be CFL. But if CFL is not closed under \intersection, that doesn't mean L_1 \intersect L_2 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 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 \subset \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 U L_2 will be CFL. But L_1 U L_2 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). After Hopcroft and Ullman.

Operation		Regular	DCFL	CFL	IND	CSL	recursive	RE
Union	w \in L_1 \lor w \in L_2\} </math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection	w \in L_1 \land w \in L_2\}</math>	Yes	No	No	No	Yes	Yes	Yes
Complement	w \not\in L_1\}</math>	Yes	Yes	No	No	Yes	Yes	No
Concatenation	w \in L_1 \land z \in L_2\}</math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Kleene star	w \in L_1 \land z \in L_1^{*}\}</math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Homomorphism		Yes	No	Yes	Yes	No	No	Yes
e-free Homomorphism		Yes	No	Yes	Yes	Yes	Yes	Yes
Substitution		Yes	No	Yes	Yes	Yes	No	Yes
Inverse Homomorphism		Yes	Yes	Yes	Yes	Yes	Yes	Yes
Reverse	w \in L\} </math>	Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection with a regular language	w \in L_1 \land w \in R\}, R \text{ regular}</math>	Yes	Yes	Yes	Yes	Yes	Yes	Yes

Tweet