Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form (Abstract only)

Share/Save/Bookmark

Asveld, P.R.J. (2005) Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form (Abstract only). [Report]

[img]
Preview
PDF
30Kb
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.
Item Type:Report
Copyright:©2005 CTIT
Research Group:
Link to this item:http://purl.utwente.nl/publications/53978
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 227387