On the context-freeness of the set of words containing overlaps

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that the set of binary words containing overlaps is not unambiguously context-free and that the set of ternary words containing overlaps is not context-free. We also show that the set of binary words that are not subwords of the Thue-Morse word is not unambiguously context-free.
8 pages

Keywords

Combinatorics, Formal Languages and Automata Theory, 68R15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/224891

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0610067
 http://arxiv.org/abs/math/0610067

Collections

arXiv