Difference between revisions of "Grammar: Decidable and Undecidable Problems"

Revision as of 17:59, 26 February 2014

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