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\colon 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 é incluso 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 é denotada como $\,_{M}Q$.

Uma ação-M é estreitamente relacionada a uma transformação de monóide. Entretanto os elementos de M não precisam ser funções por si, elas são apenas elementos de um monoide. Portanto, deve-se exigir que a ação de $\mu$ seja consistente com a multiplicação no monoide (isto é, $\mu (q,st)=\mu (\mu (q,s),t)$), como, em geral, isso não pode assegurar para algum $\mu$ arbitrário, da maneira que ele faz para a composição de função.

Uma vez que se faz essa exigência, ele está completamente seguro para queda de todos os parênteses, como o produto do monoide e a ação do monoide em um conjunto são completamente associativos. Em particular, esses elementos do monoide permitidos para serem representados como cadeia de caracteres de letras. Essa abstração nos permite falar sobre operações em cadeias de caracteres em geral, e eventualmente conduzir ao conceito de linguagem formal como sendo composta de letras.

Outra diferença entre uma ação-M e uma transformação de monoide é que para uma ação-M Q, dois elementos distintos do monoide pode determinar a mesma transformação de Q. Se nós forçamos isso não acontecer, então uma ação-M é essencialmente a mesma que um monoide de transformação.

Homomorfismo-M

Para duas ações-M $Q_{M}$ e $B_{M}$ compartilhando o mesmo monoide $M$, um homomorfismo-M $f\colon Q_{M}\to B_{M}$ é um mapeamento $f\colon Q\to B$ tal como

para todo $q\in Q$ e $m\in M$. O conjunto de todos os homomorfismos-M é comumente escrito como $\mathrm {Hom} (Q_{M},B_{M})$ ou $\mathrm {Hom} _{M}(Q,B)$.

As ações-M e homomorfismos-M juntos formam uma categoria chamada Ação-M.

Semiautômatos

Um semiautômato é uma tripla $(Q,\Sigma ,T)$ onde $\Sigma$ é um conjunto não vazio de um alfabeto de entrada, Q é um conjunto não vazio, chamado conjunto de estados, e T é a função de transição.

Quando o conjunto de estados Q é um conjunto finito (não é necessário que seja!), um semiautômato pode ser interpretado como um autômato finito determinístico $(Q,\Sigma ,T,q_{0},A)$, mas sem o estado inicial $q_{0}$ ou sem o conjunto de estados de aceitação A. . Alternativamente, isso é uma máquina de estados finitos, a qual não tem saída, e tem somente uma entrada.

Qualquer semiautômato induz uma ação de monoide da seguinte forma.

Faça $\Sigma ^{*}$ ser um monóide livre gerado por um alfabeto $\Sigma$ (de modo que * é entendido como o fecho de Kleene); isso é o conjunto de todas as palavras de tamanho finito composta de letras em $\Sigma$.

Para toda palavra w em $\Sigma ^{*}$, faça $T_{w}\colon Q\to Q$ ser a função, definida recursivamente, como se segue, para todo q em Q:

• Se $w=\varepsilon$, então $T_{\varepsilon }(q)=q$, de modo que a palavra vazia $\varepsilon$ does not change the state.

• Se $w=\sigma$ é uma letra em $\Sigma$, então $T_{\sigma }(q)=T(q,\sigma )$.

• Se $w=\sigma v$ para $\sigma \in \Sigma$ e $v\in \Sigma ^{*}$, então $T_{w}(q)=T_{v}(T_{\sigma }(q))$.

Seja $M(Q,\Sigma ,T)$ o conjunto

O conjunto $M(Q,\Sigma ,T)$ é fechado sob composição de funções; Isto é, para todo $v,w\in \Sigma ^{*}$, tem um $T_{w}\circ T_{v}=T_{vw}$. Este que também contém $T_{\varepsilon }$, que é a função identidade em Q. Uma vez que a composição de função é associativa, o conjunto $M(Q,\Sigma ,T)$ é um monoide: isto é conhecido como monóide de entrada, monóide característico, semigrupo característico ou monóide de transição do semiautômato $(Q,\Sigma ,T)$.

Propriedades

Se o conjunto de estados Q é finito, então as funções de transição são comumente representadas como tabelas de estados de transições. A construção de todas as possíveis transições alimentadas por palavras em um grupo livre tem uma representação gráfica como a dos grafos de De Brujin.

O conjunto de estados Q não precisa ser finito, nem contável. Por exemplo, semiautômatos utilizam o conceito de autômato quântico finito. O conjunto de estados Q são dados pelo espaço projetivo complexo $\mathbb {C} P^{n}$, e estados individuais são referidos como bits quânticos de n-estados. Estados de transições são dados por uma matriz unitária n×nMatriz unitária. O alfabeto de entrada $\Sigma$ permanece finito, e outra preocupação típica de teoria dos autômatos continuam. Então, o semiautômato quântico, pode ser simplesmente definido como a tripla $(\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}},\})$ quando o alfabeto $\Sigma$ tem p símbolos, de modo que existe uma matriz unitária $U_{\sigma }$ para cada símbolo $\sigma \in \Sigma$. Visto que desta maneira, é óbvio que o semiautômato quântico tem várias generalizações geométricas. Então, por exemplo, pode se tomar um espaço simétrico de Riemannian em um espaço $\mathbb {C} P^{n}$, e seleções destes grupos isométricos como funções de transição.

O monóide sintático de uma linguagem formal é isomorfo ao monoide de transição de um autômato mínimo aceitando a linguagem.

Referências

• A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups. American Mathematical Society, volume 2 (1967), ISBN 978-0-8218-0272-4.
• F. Gecseg and I. Peak, Algebraic Theory of Automata (1972), Akademiai Kiado, Budapest.
• Holcombe, W. M. L., Algebraic Automata Theory (1982), Cambridge University Press
• 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 and Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8