You do not have permission to edit this page, for the following reason:
You can view and copy the source of this page.
Templates used on this page:
Return to Grammar: Decidable and Undecidable Problems.
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 |