Loading...
Please wait, while we are loading the content...
Similar Documents
Generating all permutations by context-free grammars in Chomsky normal form
| Content Provider | CiteSeerX |
|---|---|
| Author | Asveld, Peter R. J. |
| 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 function of n. |
| File Format | |
| Publisher Institution | Theoretical Computer Science (TCS |
| Access Restriction | Open |
| Subject Keyword | Nonterminal Symbol Descriptional Complexity Context-free Grammar Gn Different Symbol Production Rule Family Gn Chomsky Normal Form Finite Language Context-free Grammar Generate Ln |
| Content Type | Text |
