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

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    5 Citations (Scopus)
    57 Downloads (Pure)

    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.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentrum voor Telematica en Informatie Technologie
    Number of pages12
    Publication statusPublished - 2007

    Publication series

    NameCTIT Technical Report Series
    No.07-28
    ISSN (Print)1381-3625

    Keywords

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

    Cite this

    Asveld, P. R. J. (2007). Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. (CTIT Technical Report Series; No. 07-28). Enschede: Centrum voor Telematica en Informatie Technologie.