Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436692 | Theoretical Computer Science | 2006 | 13 Pages |
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