Um estudo sobre linguagens formais e combinatória de palavras

Abstract

Em ciência da computação, linguagens formais são classicamente estudadas sob o ferramental da teoria de autômatos. Nesse trabalho, exploramos as propriedades de linguagens formais a partir do ferramental oferecido pela combinatória, em especial a combinatória de palavras. Em particular, exploramos a palavra infinita de Thue-Morse e sua propriedade de ser livre de cubo, bem como sua utilização para codificar partidas de xadrez.