Article ID Journal Published Year Pages File Type
437631 Theoretical Computer Science 2010 13 Pages PDF
Abstract

It is shown that every conjunctive language is generated by a conjunctive grammar from a special subclass, in which every nonterminal A has at most one rule of the general form A→α1&…&αn, while the rest of the rules for A must be of the type A→w, where w is a terminal string. For context-free grammars, a similar property does not hold (S.A. Greibach et al. (1992) [3]). If it is furthermore required that each rule A→w has a nonempty w, then a substantial subfamily of conjunctive languages can be generated, yet it remains unknown whether such grammars are as powerful as conjunctive grammars of the general form.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics