Conjunctive grammars with restricted disjunction

详细信息    查看全文

• 作者：Alex ; er Okhotin ; Christian Reitwieß ; ner
• 关键词：Conjunctive grammars ; Single tree grammars ; Normal form ; Language equations
• 刊名：Theoretical Computer Science
• 出版年：2010
• 出版时间：6 June 2010
• 年：2010
• 卷：411
• 期：26-28
• 页码：2559-2571
• 全文大小：400 K

文摘

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→α₁&…&α_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.