کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437631 690165 2010 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Conjunctive grammars with restricted disjunction
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Conjunctive grammars with restricted disjunction
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issues 26–28, 6 June 2010, Pages 2559-2571