# Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form

Asveld, P.R.J. (2006) *Generating All Circular Shifts by Context-Free Grammars in Chomsky Normal Form.* Journal of Automata, Languages and Combinatorics, 11 (2). pp. 147-159. ISSN 1430-189X

PDF Restricted to UT campus only: Request a copy 167Kb |

Abstract: | Let be an alphabet of symbols and let be the language of circular shifts of the word ; so . We discuss a few families of context-free grammars () in Chomsky normal form such that generates . The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols and the number of rules of as functions of . These and happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which and are linear. |

Item Type: | Article |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Link to this item: | http://purl.utwente.nl/publications/62108 |

Official URL: | http://jalc.de/ |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 248491