Generating All Permutations by Context-Free Grammars in Greibach Normal Form

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    65 Downloads (Pure)


    We consider context-free grammars $G_n$ in Greibach normal form and, particularly, in Greibach $m$-form ($m=1,2$) which generates the finite language $L_n$ of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). These grammars are investigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols and the number of production rules of $G_n$ as functions of $n$. As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherHuman Media Interaction (HMI)
    Number of pages22
    Publication statusPublished - 2007

    Publication series

    NameCTIT Technical Report Series
    PublisherCentre for Telematics and Information Technology, University of Twente
    ISSN (Print)1381-3625


    • METIS-245784
    • EWI-11418
    • HMI-SLT: Speech and Language Technology
    • IR-64468

    Cite this