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
|
GATECSE