Generating all Circular Shifts by Context-Free Grammars in Chomsky Normal Form
P.R.J. Asveld · University of Twente Research Information · 2006
Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular or cyclic shifts of the word $a_1a_2\ldots a_n$; so $C-n=\{a_1a_2\ldots a_{n-1}a_n,a_2a_3\ldots a_na_1,\ldots,a_na_1\ldots 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 investigated with respect to their descriptional complexity, i. e., we determine the number of nonterminal symbols $ y(n)$ and the number of rules $\pi(n)$ of $G_n$ as functions of $n$. These $ y$ 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 $ y$ and $\pi$ are linear.