Article ID Journal Published Year Pages File Type
436692 Theoretical Computer Science 2006 13 Pages PDF
Abstract

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.

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