Some remarks on a theorem of Sakarovitch

摘要

In this paper we show that there is no context-free language L such that L is an inverse image of a finite nonempty subset of a group with a noncontext-free word problem. Furthermore we can prove that any finitely generated group which is a syntactic monoid of a context-sensitive language L such that L is a union of finitely many syntactic classes always has a context-sensitive word problem.