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 language | Undefined |
---|---|
Article number | 10.1016/j.tcs.2008.09.033 |
Pages (from-to) | 565-577 |
Number of pages | 13 |
Journal | Theoretical computer science |
Volume | 409 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2008 |
Keywords
- HMI-SLT: Speech and Language Technology
- EWI-14210
- METIS-255194
- IR-62558