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

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    5 Citations (Scopus)
    103 Downloads (Pure)


    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.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages12
    Publication statusPublished - 2007

    Publication series

    NameCTIT Technical Report Series
    ISSN (Print)1381-3625


    • HMI-SLT: Speech and Language Technology
    • IR-67078
    • METIS-245697
    • EWI-9722

    Cite this