Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 103: | Line 103: | ||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
− | + | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|} | |} | ||
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 applicable, 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>.
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 |
<math>\epsilon</math>-free Homomorphism | Yes | No | Yes | Yes | Yes | Yes |
Substitution (<math>\epsilon</math>-free) | 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 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 applicable, 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>.
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 |
<math>\epsilon</math>-free Homomorphism | Yes | No | Yes | Yes | Yes | Yes |
Substitution (<math>\epsilon</math>-free) | 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 |