On the generative power of regular pattern grammars (Q794441)

This paper investigates the generative power of regular pattern grammars. It is shown that for each recursively enumerable language \(L\subseteq \Sigma^*\), \(Lc^ 5\) is a regular pattern language with \(c\not\in \Sigma\), which indicates that there exist regular pattern grammars in which selectors are commutative and prefix closed is reduced in such a way that the class of language lies strictly in between the family of EOL languages and the family of context-sensitive languages.