Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form

Asveld, P.R.J. (2006) Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form. Journal of Automata, Languages and Combinatorics, 11 (2). pp. 147-159. ISSN 1430-189X

PDF
Restricted to UT campus only: Request a copy
167Kb

Abstract:	Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular shifts of the word $a_1a_2\cdots a_n$ ; so $C_n = \{a_1a_2\cdots a_{n-1}a_n, a_2a_3\cdots a_na_1, \ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$ . We discuss a few families of context-free grammars $G_n$ ( $n\geq 1$ ) in Chomsky normal form such that $G_n$ generates $C_n$ . The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols $\nu(n)$ and the number of rules $\pi(n)$ of $G_n$ as functions of $n$ . These $\nu$ and $\pi$ happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which $\nu$ and $\pi$ are linear.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:	http://purl.utwente.nl/publications/62108
Official URL:	http://jalc.de/
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 248491