Semigrupos e monoides algébricos: uma aplicação na teoria da computação

Abstract

O objetivo deste trabalho é aplicar a teoria de semigrupos e monoides algébricos à linguagens e autômatos da teoria da computação. Para tanto, primeiramente é feito um estudo sobre semigrupos e monoides algébricos, abordando os conceitos e teoremas fundamentais da teoria. Em seguida são apresentadas as definições e resultados fundamentais relacionados com os conceitos de linguagens e autômatos da teoria da computação. Usando, principalmente, o conceito de monoide de transformação completa e o teorema fundamental do homomorfismo para semigrupos e monoides, é possível caracterizar os semigrupos e monoides livres, que são linguagens sobre um dado alfabeto. Prova-se que todo semiautômato e autômato tem, respectivamente, um semigrupo ou monoide finito associado, bem como, dado um semigrupo ou monoide finito pode-se construir um semiautômato ou autômato. Por fim, é demonstrado um teorema que caracteriza linguagem regular partindo da ideia de congruência e classes de equivalência.