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.
Grammar | <math>w \in L(M)</math> | <math>L(M) = \phi</math> | <math>L = \Sigma^*</math> | <math>L(M_1) \subseteq L(M_2)</math> | <math>L(M_1) = L(M_2)</math> | <math>L(M_1) \cap L(M_2) = \phi</math> |
---|---|---|---|---|---|---|
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 |