TCCgrad
Semigrupos e monoides algébricos: uma aplicação na teoria da computação
Fecha
2021-05-07Autor
Conzatti, Jhoni
Institución
Resumen
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.