ON REPRESENTING RECURSIVELY-ENUMERABLE LANGUAGES BY INTERNAL CONTEXTUAL LANGUAGES

We prove that each recursively enumerable language L can be written in the form L = cut(c) (L-0 boolean AND R), where L-0 is an internal con textual language, R is a regular language, and cut(c) is the operation which for a word x removes the prefix of x to the left of the unique occurrence of c in x. As corollaries of this result we obtain represen tations of recursively enumerable languages as (1) weak codings of inv erse morphic images, (2) left quotients by regular languages, and (3) images of gsm mappings of internal contextual languages. These represe ntations imply that the family of internal contextual languages, which includes the family of regular languages and is strictly included in the family of context-sensitive languages, contains languages which ca nnot be generated by programmed grammars with arbitrary rules and empt y failure fields. The case of grammars with one-sided contexts is also briefly investigated. (C) 1998 Published by Elsevier Science B.V. All rights reserved.