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

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    30 Downloads (Pure)

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

    Publication series

    NameCTIT Technical Report Series
    No.05-23
    ISSN (Print)1381-3625

    Keywords

    • IR-53978
    • circular shift
    • unambiguous grammar
    • Chomsky normal form
    • permutation
    • Context-free grammar
    • descriptional complexity
    • EWI-1880
    • METIS-227387

    Cite this