Semiautômato

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.

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.

Em livros antigos como Clifford e Preston (1967), ações-S são chamadas de “operandos”.

Em teoria das categorias, semiautômatos são essencialmente funtores.

Transformação de semigrupo e monoide de ação

Um semigrupo de transformação ou transformação de monoide é um par $(M,Q)$ 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 $m:Q\to Q$. 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. $(st)(q)=(s\circ t)(q)=s(t(q))$.

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.

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 $q\in Q$ e $s,t\in M$, então a tripla $(Q,M,\mu )$ é chamada uma ação-M à direita ou simplesmente uma ação à direita. Onde, $\mu$ é a multiplicação direita de elementos de Q por elementos de M. A ação à direita é usualmente escrita como $Q_M$.

A ação de esquerda é definida similarmente, com E sendo denotada como ${}_{M}Q$.

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.