### Abstract

For each alphabet Σ

_{n}= {a_{1},a_{2},…,a_{n}}, linearly ordered by a_{1}< a_{2}< ⋯ < a_{n}, let C_{n}be the language of circular or cyclic shifts over Σ_{n}, i.e., C_{n}= {a_{1}a_{2}⋯ a_{n-1}a_{n}, a_{2}a_{3}⋯ a_{n}a_{1},…,a_{n}a_{1}⋯ a_{n-2}a_{n-1}}. We study a few families of context-free grammars G_{n}(n ≥1) in Greibach normal form such that G_{n}generates C_{n}. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of G_{n}. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.Original language | English |
---|---|

Pages (from-to) | 1139-1149 |

Journal | International journal of foundations of computer science |

Volume | 18 |

Issue number | 6 |

DOIs | |

Publication status | Published - Dec 2007 |

### Keywords

- Context-free grammar
- EWI-11338
- IR-62000
- descriptional complexity
- HMI-SLT: Speech and Language Technology
- cyclic shift
- METIS-242033
- unambiguous grammar
- circular shift
- permutation
- Greibach normal form

## Fingerprint Dive into the research topics of 'Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form'. Together they form a unique fingerprint.

## Cite this

Asveld, P. R. J. (2007). Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form.

*International journal of foundations of computer science*,*18*(6), 1139-1149. https://doi.org/10.1142/S0129054107005182