### Abstract

_{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 |

### Fingerprint

### 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

### Cite this

*International journal of foundations of computer science*,

*18*(6), 1139-1149. https://doi.org/10.1142/S0129054107005182

}

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

**Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form.** / Asveld, Peter R.J.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

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

AU - Asveld, Peter R.J.

PY - 2007/12

Y1 - 2007/12

N2 - For each alphabet Σn = {a1,a2,…,an}, linearly ordered by a1 < a2 < ⋯ < an, let Cn be the language of circular or cyclic shifts over Σn, i.e., Cn = {a1a2 ⋯ an-1an, a2a3 ⋯ ana1,…,ana1 ⋯ an-2an-1}. We study a few families of context-free grammars Gn (n ≥1) in Greibach normal form such that Gn generates Cn. 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 Gn. 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.

AB - For each alphabet Σn = {a1,a2,…,an}, linearly ordered by a1 < a2 < ⋯ < an, let Cn be the language of circular or cyclic shifts over Σn, i.e., Cn = {a1a2 ⋯ an-1an, a2a3 ⋯ ana1,…,ana1 ⋯ an-2an-1}. We study a few families of context-free grammars Gn (n ≥1) in Greibach normal form such that Gn generates Cn. 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 Gn. 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.

KW - Context-free grammar

KW - EWI-11338

KW - IR-62000

KW - descriptional complexity

KW - HMI-SLT: Speech and Language Technology

KW - cyclic shift

KW - METIS-242033

KW - unambiguous grammar

KW - circular shift

KW - permutation

KW - Greibach normal form

U2 - 10.1142/S0129054107005182

DO - 10.1142/S0129054107005182

M3 - Article

VL - 18

SP - 1139

EP - 1149

JO - International journal of foundations of computer science

JF - International journal of foundations of computer science

SN - 0129-0541

IS - 6

ER -