Semi autômato

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde setembro de 2013).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

Em matemática e ciência da computação teórica, um semi autômatoé um autômato finito determinístico ter entradas mas não há saída. Trata-se de um set Q de estados, um conjunto S chamado o alfabeto de entrada, e uma função T: Q × S ? Q chamada a função de transição.

Associado a qualquer semi autômato é um monoid chamado caracteristica monoid, entrada monoid, transição monoid ou transição de sistema do semi autômato, que atos sobre o conjunto de estados Q. Isto pode ser visto tanto como uma ação de monoid livre de strings no alfabeto de entrada S, ou como a induzida transformação semigrupo de Q.

Nos livros mais antigos, como Clifford e Preston (1967) S atos são chamados de "operando".

Em teoria da categoria, semiautomata são essencialmente functor s.


Semigroups transformação e atos monoid[editar | editar código-fonte]

A transformação semigrupo ou transformação monoid é o par (M,Q) consistindo de um set Q (muitas vezes chamado de "conjunto de estados") e um semigrupo ou monoid M de funções, ou "transformações", mapeando Q a si mesmo. Eles são funções no sentido de que cada elemento m de M é um mapa m\colon Q\to Q. se s e t são duas funções diferentes da transformação semigrupo, então o produto semigrupo segue trivialmente a partir de composição de função, de modo que se define (st)(q) como (s\circ t)(q)=s(t(q)).

Alguns autores consideram "semigrupo" e "monoid" como sinônimos. Aqui não um semigrupo precisa ter um elemento da identidade, um monoid é um semigrupo com um elemento de identidade. Dado que o conceito de funções que actuam sobre um conjunto inclui sempre a noção de uma função de identidade, que quando aplicada ao conjunto não faz nada, uma transformação semigroup pode ser feita em um monoid tendo a sua união com a função de identidade.

M- atos[editar | editar código-fonte]

Faça M ser o monoid e Q ser um conjunto não vazio. Se existe uma operação multiplicativo

\mu\colon Q\times M \to Q
(q,m)\mapsto qm=\mu(q,m)

que satisfaz as propriedades

q1=q

para 1 unidade do monoid, e

q(st)=(qs)t

para todo q\in Q e s,t\in M, então a tripla (Q,M,\mu) é chamada M- atos certos ou simplesmente um atos certos. Na mão longa, \mu é o multiplicação direito de elementos de Q por elementos de M. O ato certo é muitas vezes escrita como Q_M.

o ato esquerdo é definido de forma semelhante, com a

\mu\colon M\times Q \to Q
(m,q)\mapsto mq=\mu(m,q)

e é muitas vezes indicado como \,_MQ.

Um M-atosestá intimamente relacionada com uma monoid transformação. No entanto, os elementos de M não precisa de ser funções per se, Eles são apenas alguns elementos de monoids. Portanto, deve-se exigir que a ação de \mu ser compatível com a multiplicação nas monoides (por exemplo \mu(q, st)=\mu(\mu(q,s),t)),como, em geral, isto pode não manter por algum arbitrário \mu, que da maneira que ele faz para a composição da função.

Um Faz Uma vez que essa demanda, é completamente seguro para soltar todos os parênteses, como os monoids produtos ea ação dos monoids são completamente no set associativa. Em particular, isso permite que elementos dos monoids a ser representado como string de cartas, no sentido de ciência da computação da palavra "seqüência". Essa abstração, então, permite uma para falar sobre operação string s em geral, e, eventualmente, leva ao conceito de linguagens formais Composto de Ser como seqüências de letras.

Outra diferença entre uma M-atos Isto é em monoides transformação e para uma M-atos Q, dois elementos distintos dos monoids de Maio, determinou a transformação do Mesmo Q. Se exigimos que isso não aconteça, então um M-atos Essencialmente, é o mesmo que em monoids transformação.

M-homomorfismos[editar | editar código-fonte]

Um M--homomorfismo um mapa

f\colon Q_M\to B_M

de tal modo que

f(qm)=f(q)m

para todo q\in Q e m\in M. O conjunto de todos M-homomorfismos é geralmente escrita como\mathrm{Hom}(Q_M, B_M) or \mathrm{Hom}_M(Q, B).

O M-atos e M-homomorfismo juntos formam um categoria chamado M-atos.

Semi autômato[editar | editar código-fonte]

O semi autômato é a tripla (Q,\Sigma,T) onde \Sigma é um grupo não-vazia, o chamado alfabeto de entrada, Q é um grupo não-vazia, o chamado conjunto de estados, eT é função de transição

T\colon Q\times \Sigma \to Q.

Quando o conjunto de estados Q é um conjunto finito (não precisa de ser!), um semi autômato pode ser pensado como uma determinista autómato finito (Q,\Sigma,T,q_0,A), mas sem o estado inicial q_0 ou um conjunto de aceitar estados A. Alternativamente, é um máquina de estado finito, que não tem saída, e apenas uma entrada.

Qualquer semiautomaton induz um ato de um monoid da seguinte maneira.

Faça \Sigma^* ser o [monoid livre]] gerado pelo alfabeto \Sigma (para que o sobrescrito * Entende-se o Kleene estrela), é o conjunto de todos os finito de comprimento strings, composto das 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 todos q em Q:

  • se w=\sigma É uma letra no \Sigma, então T_\sigma(q)=T(q,\sigma).
  • se w=\sigma v for \sigma\in\Sigma e v\in \Sigma^*, entao T_w(q)=T_v(T_\sigma(q)).

faça M(Q,\Sigma,T) o conjunto

M(Q,\Sigma,T)=\{T_w \vert w\in\Sigma^* \}.

O conjunto M(Q,\Sigma,T) é fechado em composição de função, isto é, para todos v,w\in\Sigma^*, tem umvT_w\circ T_v=T_{vw}. Ele também contém T_\varepsilon,que é o função identidade em S. Desde composição função é associativo, o conjunto M(Q,\Sigma,T) é um monoid: é denominado entrada monoid, caracteristica monoid, caracteristica semigrupo ou transição monoiddo 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 geralmente representada como Tabela de transição de estados s. A construção de todas as transições possíveis impulsionado por cordas no grupo livre tem uma representação gráfica de como Bruijn gráficos.

O conjunto de estados Q não precisa ser finito, ou mesmo contável. Como um exemplo, semiautomata sustentam o conceito de quântico finito autómatos. Lá, o conjunto de estados Q são dadas pela espaço projetivo complexo \mathbb{C}P^n,e os estados individuais são referidos como n-state qubits. Transições de estado são dadas por unitária n &tempo n matrizes. O alfabeto de entrada \Sigmapermanece finito, e outras preocupações típicas da teoria dos autômatos permanecer no jogo. Assim, o quântico semi autómato pode ser simplesmente definido como o tripla (\mathbb{C}P^n,\Sigma,\{U_{\sigma_1},U_{\sigma_2},\dotsc,U_{\sigma_p},\}) quando o alfabeto \Sigma tem p letras, então existe uma matriz unitária U_\sigma para cada letra \sigma\in\Sigma. Dito desta maneira, é óbvio que o quântico semiautomaton tem muitas generalizações geométricas. Assim, por exemplo, pode-se tomar um espaço simétrica riemanniano em lugar de \mathbb{C}P^n,e seleções de seu grupo de isometrias como as funções de transição.

O sintática monoid de Linguagem formais e isomorfo de para o monoid Transição de Mínimo Automato Aceitar o idioma.

Referencias[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