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...") |
Arjun Suresh (talk | contribs) |
||
Line 7: | Line 7: | ||
|- | |- | ||
! Operation | ! Operation | ||
− | |||
! Regular | ! Regular | ||
− | ! | + | ! DCFL |
− | ! | + | ! CFL |
− | ! | + | ! CSL |
− | + | ! Recursive | |
− | ! | + | ! RE |
− | ! | ||
|- | |- | ||
− | | | + | |Union |
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 27: | Line 24: | ||
|- | |- | ||
|[[Intersection (set theory)|Intersection]] | |[[Intersection (set theory)|Intersection]] | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 37: | Line 33: | ||
|- | |- | ||
|[[Complement (set theory)|Complement]] | |[[Complement (set theory)|Complement]] | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
Line 47: | Line 42: | ||
|- | |- | ||
|[[Concatenation]] | |[[Concatenation]] | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 57: | Line 51: | ||
|- | |- | ||
|Kleene star | |Kleene star | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 67: | Line 60: | ||
|- | |- | ||
|Homomorphism | |Homomorphism | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 77: | Line 69: | ||
|- | |- | ||
|e-free Homomorphism | |e-free Homomorphism | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 87: | Line 78: | ||
|- | |- | ||
|Substitution | |Substitution | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 97: | Line 87: | ||
|- | |- | ||
|Inverse Homomorphism | |Inverse Homomorphism | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
Line 107: | Line 96: | ||
|- | |- | ||
|Reverse | |Reverse | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 117: | Line 105: | ||
|- | |- | ||
|Intersection with a [[regular language]] | |Intersection with a [[regular language]] | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
Line 128: | Line 115: | ||
|- | |- | ||
|Min | |Min | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
Line 138: | Line 124: | ||
|- | |- | ||
|Max | |Max | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
Line 148: | Line 133: | ||
|- | |- | ||
|Init | |Init | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 158: | Line 142: | ||
|- | |- | ||
|Cycle | |Cycle | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
Line 168: | Line 151: | ||
|- | |- | ||
|Shuffle | |Shuffle | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{?}} | | {{?}} | ||
Line 178: | Line 160: | ||
|- | |- | ||
|Perfect Shuffle | |Perfect Shuffle | ||
− | |||
| {{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 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.
Operation | Regular | DCFL | CFL | CSL | Recursive | RE | |
---|---|---|---|---|---|---|---|
Union | Yes | No | Yes | Yes | Yes | Yes | Yes |
Intersection | Yes | No | No | No | Yes | Yes | Yes |
Complement | Yes | Yes | No | No | Yes | Yes | No |
Concatenation | Yes | No | Yes | Yes | Yes | Yes | Yes |
Kleene star | 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 | Yes | No | Yes | Yes | Yes | Yes | Yes |
Intersection with a regular language | Yes | 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 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.
Operation | Regular | DCFL | CFL | CSL | Recursive | RE | |
---|---|---|---|---|---|---|---|
Union | Yes | No | Yes | Yes | Yes | Yes | Yes |
Intersection | Yes | No | No | No | Yes | Yes | Yes |
Complement | Yes | Yes | No | No | Yes | Yes | No |
Concatenation | Yes | No | Yes | Yes | Yes | Yes | Yes |
Kleene star | 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 | Yes | No | Yes | Yes | Yes | Yes | Yes |
Intersection with a regular language | Yes | Yes | Yes | Yes | Yes | Yes | Yes |