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

Revision as of 17:55, 26 February 2014

Closure properties of language families

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