کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436692 690025 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generating all permutations by context-free grammars in Chomsky normal form
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Generating all permutations by context-free grammars in Chomsky normal form
چکیده انگلیسی

Let Ln be the finite language of all n! strings that are permutations of n different symbols (n⩾1). We consider context-free grammars Gn in Chomsky normal form that generate Ln. In particular we study a few families {Gn}n⩾1, satisfying L(Gn)=Ln for n⩾1, with respect to their descriptional complexity, i.e. we determine the number of nonterminal symbols and the number of production rules of Gn as functions of n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 354, Issue 1, 21 March 2006, Pages 118-130