Representation Theorem Using DOS Languages ; CU-CS-161-79
Andrzej Ehrenfeucht, Grzegorz Rozenberg · CU Scholar (University of Colorado Boulder) · 1979
It is demonstrated that every context-free language is a homomorphic image of the intersection of two DOS languages and that every recursively enumerable language is the homomorphic image of the intersection of three DOS languages. It is also proved that by increasing the number of components in the intersections of DOS languages one gets an infinite hierarchy of classes of languages within the class of context-sensitive languages.