Em matemática e ciência da computação teórica, um semiautômato é um autômato finito determinístico que tem entradas mas não tem saídas. Isto consiste de um conjunto Q de estados, um alfabeto de entrada Σ, e uma função T: Q × Σ → Q chamado de função de transição. Clifford, A. H. e Preston, G. B., The Algebraic Theory of Semigroups. American Mathematical Society, volume 2 (1967), ISBN 978-0-8218-0272-4.
Associado a qualquer semiautômato está um monoide chamado monoide de característica, monoide de entrada, monoide de transição ou sistema de transição do semiautômato, que atua sobre o conjunto de estados Q. Isso pode ser visto tanto como uma ação do monoide livre de uma cadeia de caracteres na entrada do alfabeto Σ, ou como uma transformação de semigrupo de Q. Holcombe, W. M. L., Algebraic Automata Theory. Cambridge University Press (1982).
Em livros antigos como Clifford e Preston (1967), ações-S são chamadas de “operandos”. Clifford, A. H. e Preston, G. B., The Algebraic Theory of Semigroups. American Mathematical Society, volume 2 (1967), ISBN 978-0-8218-0272-4.
Em teoria das categorias, semiautômatos são essencialmente funtores. F. Gecseg e I. Peak, Algebraic Theory of Automata (1972), Akademiai Kiado, Budapest.
Transformação de semigrupo e monoide de ação Um semigrupo de transformação ou transformação de monoide é um par consistindo de um conjunto de Q (também chamado de “conjunto de estados”) e um semigrupo ou monoide M de funções, ou “transformações”, mapeando Q em si próprio. Eles são funções no sentido de que todo elemento m de M é um mapeamento . Se s e t são duas funções de um semigrupo de transformação, o produto deles é definido como sua composição de função. . J. M. Howie, Automata and Languages, (1991), Clarendon Press, ISBN 0-19-853442-6.
Alguns autores consideram “semigrupo” e “monoide” como sinônimos. Aqui um semigrupo não precisa ter um elemento identidade; um monoide é um semigrupo com um elemento identidade (também conhecido como “unidade”). Desde a noção de funções agindo sob um conjunto sempre inclui a noção de uma função identidade, que, quando aplicada ao conjunto, não faz nada, um semigrupo de transformação pode ser feito em um monoide adicionando a função identidade. Rudolf Lidl e Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8.
Ações-M Seja M um monoide e Q um conjunto não vazio. Se existe uma operação de multiplicação que satisfaz a propriedade para 1, a unidade do monoide, e para todo e , então a tripla é chamada uma ação-M à direita ou simplesmente uma ação à direita. Onde, é a multiplicação direita de elementos de Q por elementos de M. A ação à direita é usualmente escrita como . Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories (2000), Walter de Gruyter, Berlin, ISBN 3-11-015248-7.
A ação de esquerda é definida similarmente, com E sendo denotada como . Rudolf Lidl e Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8.
Referências A. H. Clifford e G. B. Preston, The Algebraic Theory of Semigroups. American Mathematical Society, volume 2 (1967), ISBN 978-0-8218-0272-4. F. Gecseg e I. Peak, Algebraic Theory of Automata (1972), Akademiai Kiado, Budapest. Holcombe, W. M. L., Algebraic Automata Theory. Cambridge University Press (1982). J. M. Howie, Automata and Languages, (1991), Clarendon Press, ISBN 0-19-853442-6. Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories (2000), Walter de Gruyter, Berlin, ISBN 3-11-015248-7. Rudolf Lidl e Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8.
Categoria:Teoria dos autômatos Categoria:Teoria das categorias Categoria:Linguagens formais Categoria:Teoria de semigrupos