CHARACTERIZATIONS OF RE LANGUAGES STARTING FROM INTERNAL CONTEXTUAL LANGUAGES

We investigate the problem of expressing an arbitrary recursively enum erable language L-0 in terms of an internal contextual language. It ha s been shown previously that L-0 is a gsm image of a language generate d by an internal contextual grammar with finite selectors. We first pr ove several variants of this characterization of recursively enumerabl e languages. We then establish two entirely new characterizations in t erms of internal contextual grammars with finite selectors, applying e ither (1) leftmost (or prefix) derivations, or (2) erased contexts. Th e characterization obtained in (2) is particularly simple because one- sided grammars are sufficient in this case.