Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 1: | Line 1: | ||
− | 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>\ | + | 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 \union L_2</math> will be CFL. But if CFL is not closed under \intersection, that doesn't mean <math>L_1 \intersection 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 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. | Now, while applying closure property do remember the language hierarchy. |
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 \union L_2</math> will be CFL. But if CFL is not closed under \intersection, that doesn't mean <math>L_1 \intersection 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 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 U L_2</math> will be CFL. But <math>L_1 U L_2</math> may also be regular, which closure property can't tell.
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 |
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 \union L_2</math> will be CFL. But if CFL is not closed under \intersection, that doesn't mean <math>L_1 \intersection 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 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 U L_2</math> will be CFL. But <math>L_1 U L_2</math> may also be regular, which closure property can't tell.
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 |