On representing RE languages by one-sided internal contextual languages

摘要

In this paper we prove that each recursively enumerable language L can be written in the form L = cut_d(L' ∩ R), where L' is a language generated by a one-sided internal contextual grammar with context-free choice, R is a regular language, and cut_d is the operation which removes the prefix bounded by the special symbol d, which appears exactly once in the strings for which cutd is denned. However, the context-free choice sets are always deterministic linear languages of a very simple form. Similar representations can be obtained using one-sided contextual grammars with finite choice and with erased or with erasing contexts.