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

P.R.J. Asveld

    Research output: Book/ReportReportProfessional

    63 Downloads (Pure)

    Abstract

    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
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages22
    Publication statusPublished - 2007

    Publication series

    NameCTIT Technical Report Series
    PublisherCentre for Telematics and Information Technology, University of Twente
    No.FS-07-05/TR-CTIT-07-83
    ISSN (Print)1381-3625

    Keywords

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

    Cite this