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.
|Place of Publication||Enschede|
|Publisher||Human Media Interaction (HMI)|
|Number of pages||22|
|Publication status||Published - 2007|
|Name||CTIT Technical Report Series|
|Publisher||Centre for Telematics and Information Technology, University of Twente|
- HMI-SLT: Speech and Language Technology
Asveld, P. R. J. (2007). Generating All Permutations by Context-Free Grammars in Greibach Normal Form. (CTIT Technical Report Series; No. FS-07-05/TR-CTIT-07-83). Enschede: Human Media Interaction (HMI).