Characterizations of re languages starting from internal contextual languages ^∗

^∗Research supported by the Academy of Finland, project 11281, and the EPSPRIT Basic Research Working Group ASMICS II

Abstract

We investigate the problem of expressing an arbitrary recursively enumerable language L ₀in terms of an internal contextual language. It has been shown previously that L ₀is a gsm image of a language generated by an internal contextual grammar with finite selectors. We first prove several variants of this characterization of recursively enumerable languages. We then establish two entirely new characterizations in terms of internal contextual grammars with finite selectors, applying either (1) leftmost (or prefix) derivations, or (2) erased contexts. The characterization obtained in (2) is particularly simple because one-sided grammars are sufficient in this case.

Keywords:

• Contextual grammars
• recursively enumerable languages
• twin-shuffle language
• leftmost derivation
• Chomsky hierarchy

C.R. Categories:

• F.4.3
• F.1.1

^∗Research supported by the Academy of Finland, project 11281, and the EPSPRIT Basic Research Working Group ASMICS II

^∗Research supported by the Academy of Finland, project 11281, and the EPSPRIT Basic Research Working Group ASMICS II

Notes

^∗Research supported by the Academy of Finland, project 11281, and the EPSPRIT Basic Research Working Group ASMICS II