Máquina Moore - Moore machine

Na teoria da computação , uma máquina de Moore é uma máquina de estado finito cujos valores de saída são determinados apenas por seu estado atual . Isso está em contraste com uma máquina de Mealy , cujos valores de saída são determinados por seu estado atual e pelos valores de suas entradas. A máquina de Moore tem o nome de Edward F. Moore , que apresentou o conceito em um artigo de 1956, " Experimentos de Gedanken em máquinas sequenciais".

Definição formal

Uma máquina Moore pode ser definida como uma 6 tupla consistindo no seguinte: ${\ displaystyle (Q, q_ {0}, \ Sigma, O, \ delta, G)}$

• Um conjunto finito de estados ${\ displaystyle Q}$
• Um estado inicial (também chamado de estado inicial) que é um elemento de${\ displaystyle q_ {0}}$${\ displaystyle Q}$
• Um conjunto finito chamado alfabeto de entrada ${\ displaystyle \ Sigma}$
• Um conjunto finito chamado alfabeto de saída ${\ displaystyle O}$
• Uma função de transição que mapeia um estado e o alfabeto de entrada para o próximo estado${\ displaystyle \ delta: Q \ times \ Sigma \ rightarrow Q}$
• Uma função de saída que mapeia cada estado para o alfabeto de saída${\ displaystyle G: Q \ rightarrow O}$

Uma máquina de Moore pode ser considerada um tipo restrito de transdutor de estado finito .

Representação visual

Mesa

A tabela de transição de estado é uma tabela que mostra a relação entre uma entrada e um estado.

Diagrama

O diagrama de estado de uma máquina de Moore ou diagrama de Moore é um diagrama que associa um valor de saída a cada estado. A máquina Moore é um produtor de saída.

Relacionamento com máquinas Mealy

Como as máquinas Moore e Mealy são tipos de máquinas de estado finito, elas são igualmente expressivas: qualquer um dos tipos pode ser usado para analisar uma linguagem regular .

A diferença entre as máquinas Moore e as máquinas Mealy é que, na última, a saída de uma transição é determinada pela combinação do estado atual e a entrada atual ( como a entrada para ), em oposição a apenas o estado atual ( como a entrada para ) . Quando representado como um diagrama de estado , ${\ displaystyle S \ times \ Sigma}$${\ displaystyle G}$${\ displaystyle S}$${\ displaystyle G}$

• para uma máquina de Moore, cada nó (estado) é rotulado com um valor de saída;
• para uma máquina Mealy, cada arco (transição) é rotulado com um valor de saída.

Cada máquina de Moore é equivalente à máquina de Mealy com os mesmos estados e transições e a função de saída , que pega cada par de entrada de estado e produz , onde é a função de saída e é a função de transição. ${\ displaystyle M}$${\ displaystyle G (s, \ sigma) \ rightarrow G_ {M} (\ delta _ {M} (s, \ sigma))}$${\ displaystyle (s, \ sigma)}$${\ displaystyle G_ {M} (\ delta _ {M} (s, \ sigma))}$${\ displaystyle G_ {M}}$${\ displaystyle M}$${\ displaystyle \ delta _ {M}}$${\ displaystyle M}$

No entanto, nem toda máquina Mealy pode ser convertida em uma máquina Moore equivalente. Alguns podem ser convertidos apenas em uma máquina de Moore quase equivalente, com saídas alteradas no tempo. Isso se deve ao modo como os rótulos de estado são emparelhados com os rótulos de transição para formar os pares de entrada / saída. Considere uma transição de um estado para outro . A entrada que causa a transição rotula a borda . A saída correspondente a essa entrada é o rótulo do estado . Observe que este é o estado de origem da transição. Portanto, para cada entrada, a saída já está fixada antes que a entrada seja recebida e depende apenas do estado atual. Esta é a definição original de E. Moore. É um erro comum usar o rótulo de estado como saída para a transição . ${\ displaystyle s_ {i} \ rightarrow s_ {j}}$${\ displaystyle s_ {i}}$${\ displaystyle s_ {j}}$${\ displaystyle s_ {i} \ rightarrow s_ {j}}$${\ displaystyle (s_ {i}, s_ {j})}$${\ displaystyle s_ {i}}$${\ displaystyle s_ {j}}$${\ displaystyle s_ {i} \ rightarrow s_ {j}}$

Exemplos

Tipos de acordo com o número de entradas / saídas.

Simples

As máquinas Moore simples têm uma entrada e uma saída:

• detector de borda usando XOR
• máquina de somar binária
• sistemas sequenciais com clock (uma forma restrita de máquina de Moore onde o estado muda apenas quando o sinal de relógio global muda)

A maioria dos sistemas eletrônicos digitais são projetados como sistemas sequenciais com clock . Os sistemas sequenciais com clock são uma forma restrita de máquina de Moore, onde o estado muda apenas quando o sinal de clock global muda. Normalmente, o estado atual é armazenado em flip-flops e um sinal de relógio global é conectado à entrada de "relógio" dos flip-flops. Os sistemas sequenciais com clock são uma forma de resolver problemas de metaestabilidade . Uma máquina de Moore eletrônica típica inclui uma cadeia lógica combinatória para decodificar o estado atual nas saídas (lambda). No instante em que o estado atual muda, essas mudanças se propagam por essa cadeia e quase instantaneamente a saída é atualizada. Existem técnicas de design para garantir que nenhuma falha ocorra nas saídas durante aquele breve período enquanto essas mudanças estão se propagando pela cadeia, mas a maioria dos sistemas é projetada de forma que falhas durante esse breve período de transição sejam ignoradas ou irrelevantes. As saídas então permanecem as mesmas indefinidamente ( LEDs permanecem brilhantes, energia permanece conectada aos motores, solenóides permanecem energizados, etc.), até que a máquina de Moore mude de estado novamente.

Exemplo Trabalhado

Uma rede sequencial possui uma entrada e uma saída. A saída torna-se 1 e permanece 1 depois disso quando pelo menos dois 0's e dois 1's ocorreram como entradas.

Máquina moore de exemplo

Uma máquina Moore com nove estados para a descrição acima é mostrada à direita. O estado inicial é o estado A e o estado final é o estado I. A tabela de estados para este exemplo é a seguinte:

Complexo

Máquinas Moore mais complexas podem ter várias entradas, bem como várias saídas.

Experimentos de Gedanken

No artigo de Moore " Experimentos de Gedanken em máquinas sequenciais", os autômatos (ou máquinas) são definidos como tendo estados, símbolos de entrada e símbolos de saída. Nove teoremas são provados sobre a estrutura e experimentos com . Mais tarde, as " máquinas" ficaram conhecidas como "máquinas de Moore". ${\ displaystyle (n; m; p)}$${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle p}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$

No final do artigo, na seção "Problemas adicionais", a seguinte tarefa é declarada:

Outro problema que se segue diretamente é o aprimoramento dos limites dados nos teoremas 8 e 9.

O Teorema de Moore 8 é formulado como:

Dada uma máquina arbitrária , de modo que cada dois de seus estados sejam distinguíveis um do outro, existe um experimento de comprimento que determina o estado de no final do experimento.${\ displaystyle (n; m; p)}$${\ displaystyle S}$${\ displaystyle {\ tfrac {n (n-1)} {2}}}$${\ displaystyle S}$

Em 1957, AA Karatsuba provou os dois teoremas a seguir, que resolveram completamente o problema de Moore sobre o aprimoramento dos limites do comprimento do experimento de seu "Teorema 8".

Teorema A. Se for uma máquina, de modo que cada dois de seus estados sejam distinguíveis um do outro, então existe um experimento ramificado de comprimento máximo através do qual se pode determinar o estado de no final do experimento.${\ displaystyle S}$${\ displaystyle (n; m; p)}$${\ displaystyle {\ tfrac {(n-1) (n-2)} {2}} + 1}$${\ displaystyle S}$

Teorema B. Existe uma máquina, em que cada dois estados são distinguíveis um do outro, de modo que a duração dos experimentos mais curtos que estabelecem o estado da máquina no final do experimento é igual a .${\ displaystyle (n; m; p)}$${\ displaystyle {\ tfrac {(n-1) (n-2)} {2}} + 1}$

Os teoremas A e B serviram de base ao trabalho de curso de um aluno do quarto ano, AA Karatsuba, "Sobre um problema da teoria dos autômatos", que foi distinguido por referência testemunhal no concurso de trabalhos de alunos da faculdade de mecânica e matemática da Moscow Lomonosow State University em 1958. O artigo de Karatsuba foi entregue ao jornal Uspekhi Mat. Nauk em 17 de dezembro de 1958 e foi publicado em junho de 1960.

Até os dias atuais (2011), o resultado de Karatsuba sobre a duração dos experimentos é o único resultado não linear exato, tanto na teoria dos autômatos quanto em problemas semelhantes da teoria da complexidade computacional.

Veja também

• Circuito síncrono
• Maquina de farelo
• Máquina de estado algorítmico
• Sistema autônomo (matemática)

Referências

Leitura adicional

• Conway, JH (1971). Álgebra regular e máquinas finitas . Londres: Chapman e Hall. ISBN 0-412-10620-5. Zbl  0231.94041 .
• Moore EF Gedanken-experimentos em máquinas sequenciais. Automata Studies, Annals of Mathematical Studies, 34, 129-153. Princeton University Press, Princeton, NJ (1956).
• Karatsuba AA Solução de um problema da teoria dos autômatos finitos. Usp. Esteira. Nauk, 15: 3, 157-159 (1960).
• Karatsuba AA Experimente mit Automaten (alemão) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).
• Karatsuba AA Lista de trabalhos de pesquisa .

Moore-and-Mealy-Machine

links externos

• Mídia relacionada à máquina Moore no Wikimedia Commons