Difference between revisions of "Closure Property of Language Families"

Line 4: Line 4:
  
 
:{| class="wikitable"
 
:{| class="wikitable"
−
|+ align="top"|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.
+
|+ align="top"|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
 
! Operation
Line 17: Line 17:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 25: Line 24:
 
|Intersection
 
|Intersection
 
| {{Yes}}
 
| {{Yes}}
−
| {{No}}
 
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
Line 35: Line 33:
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
−
| {{No}}
 
 
| {{No}}
 
| {{No}}
 
| {{Yes}}
 
| {{Yes}}
Line 44: Line 41:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 53: Line 49:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 62: Line 57:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
Line 71: Line 65:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 80: Line 73:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 87: Line 79:
 
|-
 
|-
 
|Inverse Homomorphism
 
|Inverse Homomorphism
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 98: Line 89:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 105: Line 95:
 
|-
 
|-
 
|Intersection with a [[regular language]]
 
|Intersection with a [[regular language]]
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 118: Line 107:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{?}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 127: Line 115:
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{?}}
 
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
|-
 
|-
−
|Init
 
−
| {{Yes}}
 
−
| {{No}}
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{No}}
 
−
| {{No}}
 
−
| {{Yes}}
 
−
|-
 
−
|Cycle
 
−
| {{Yes}}
 
−
| {{No}}
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
|-
 
−
|Shuffle
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
|-
 
−
|Perfect Shuffle
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{Yes}}
 
 
-->
 
-->
 
|}
 
|}

Revision as of 11:49, 26 February 2014

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).
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
Retrieved from "https://gatecse.in/w/index.php?title=Closure_Property_of_Language_Families&oldid=2610"

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).
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