Terminal context in context-sensitive grammars.

Abstract

Investigation of the conditions whereunder context-sensitive grammars generate context-free languages. The obtained results indicate that, if every noncontext-free rewriting rule of a context-sensitive grammar has as left context a string of terminal symbols and the left context is at least as long as the right context, then the language generated is context-free. Likewise, if every noncontext-free rewriting rule of a context-sensitive grammar has strings of terminal symbols as left and right contexts, then the language generated is also context-free.