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

Asveld, P.R.J. (2007) Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. International journal of foundations of computer science, 18 (6). pp. 1139-1149. ISSN 0129-0541

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

Abstract:	For each alphabet $\Sigma_n=\{a_1,a_2,\ldots,a_n\}$ , linearly ordered by $a_1<a_2<\cdots<a_n$ , let $C_n$ be the language of circular or cyclic shifts over $\Sigma_n$ , i.e., $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 study a few families of context-free grammars $G_n$ ( $n\geq1$ ) in Greibach normal form such that $G_n$ generates $C_n$ . The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals $\nu(n)$ , the number of rules $\pi(n)$ and the number of leftmost derivations $\delta(n)$ of $G_n$ . As in the case of Chomsky normal form, these $\nu$ , $\pi$ and $\delta$ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal with respect to all these measures remains open.
Item Type:	Article
Copyright:	© 2007 World Scientific
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Human Media Interaction (HMI)
Link to this item:	http://purl.utwente.nl/publications/62000
Official URL:	http://dx.doi.org/10.1142/S0129054107005182
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 242033