On simple generators of recursively enumerable languages

• Polynomial generators for recursively enumerable languages.
• The languages REP={(amb)n|m,n∈N}REP={(amb)n|m,n∈N} and BREP={(anb)n|n∈N}BREP={(anb)n|n∈N} possess a catenation closure property.
• Applying classical number theory results in formal languages.

For each language L  , let Fˆ∩(L) (Cˆ∩(L), resp.) be the intersection-closed full AFL (full trio, resp.) generated by L  . Furthermore, for each natural number k≥2k≥2 let Pk={ank|n∈N}Pk={ank|n∈N}. By applying certain classical and recent results on Diophantine equations we show that LRE=Fˆ∩(Pk), where LRELRE is the family of all recursively enumerable languages. This allows us to answer to an open problem of S. Ginsburg and J. Goldstine in [3]. A general method to reduce certain restricted membership problems in language families to number theory (in particular to systems of Diophantine equations) is then considered. In the third part of the paper, we show that the Cˆ∩(REP)=Cˆ∩(BREP)=LRE where REP={(amb)n|m,n∈N}REP={(amb)n|m,n∈N} and BREP={(anb)n|n∈N}BREP={(anb)n|n∈N}. The results give an answer to two problems left open by P. Turakainen in [11].