On grammars with local and global context conditions

Abstract

We introduce the notion of an 1CF grammar (a context-free grammar with local context conditions) and illustrate that it is a common generalization of some well-known types of grammars with context conditions. We examine the simplicity of the presentation of the context conditions and the possibility of the reduction of the number of context checks. We show that every context-sensitive (recursively enumerable) language can be generated by a grammar with periodic check of identical sets of forbidding context conditions with periods of constant length.

Keywords:

• Grammars with context conditions
• recursively enumerable languages
• formal language theory

C.R.Categories:

• F.4.2.1