### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Human Media Interaction (HMI) |

Number of pages | 22 |

Publication status | Published - 2007 |

### Publication series

Name | CTIT Technical Report Series |
---|---|

Publisher | Centre 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

*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).

}

*Generating All Permutations by Context-Free Grammars in Greibach Normal Form*. CTIT Technical Report Series, no. FS-07-05/TR-CTIT-07-83, Human Media Interaction (HMI), Enschede.

**Generating All Permutations by Context-Free Grammars in Greibach Normal Form.** / Asveld, P.R.J.

Research output: Book/Report › Report › Professional

TY - BOOK

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

AU - Asveld, P.R.J.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - METIS-245784

KW - EWI-11418

KW - HMI-SLT: Speech and Language Technology

KW - IR-64468

M3 - Report

T3 - CTIT Technical Report Series

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

PB - Human Media Interaction (HMI)

CY - Enschede

ER -