Semi autômato

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática e ciência da computação teórica, um semi autô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 semi autômato está um monóide chamado monóide de característica, monóide de entrada, monóide de transição ou sistema de transição do semi autômato, que atua sobre o conjunto de estados Q. Isso pode ser visto tanto como uma ação do monóide 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, semi autômatos são essencialmente funtores.

Transformação de semigrupo e monóide de ação[editar | editar código-fonte]

Um semigrupo de transformação ou transformação de monóide é 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 “monóide” como sinônimos. Aqui um semigrupo não precisa ter um elemento identidade; um monóide é 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 indentidade.

Ações-M[editar | editar código-fonte]

Seja M um monóide 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 \,_MQ.

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 caraceteres 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[editar | editar código-fonte]

Para duas ações-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.

Semi Autômatos[editar | editar código-fonte]

Um semi autô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 semi autô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 semi-automato 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 semi autômato (Q,\Sigma,T).

Propriedades[editar | editar código-fonte]

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, semi autô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×n. O alfabeto de entrada \Sigma permanece finito, e outra preocupação típica de teoria dos autômatos continuam. Então, o semi autô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 semi autô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 monóide de transição de um autômato mínimo aceitando a linguagem.

Referências[editar | editar código-fonte]

  • 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