Generating all permutations by context-free grammars in Chomsky normal form

AbstractLet 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