Maquina de moore

Na ciência da computação teórica , notadamente na teoria dos autômatos e na teoria da computabilidade , uma máquina de Moore ou autômato de Moore (proposto por Edward F. Moore ) é um transdutor finito (ou seja, um autômato finito com uma saída) para o qual as saídas dependem apenas do Estado atual. Isso significa que cada estado possui uma letra de saída. A carta é emitida quando o status é alcançado. Em particular, o comprimento da palavra de saída é igual ao comprimento da palavra de entrada.

Essa definição é mais restritiva do que a das máquinas Mealy, para as quais os valores de saída dependem do estado atual e da letra de entrada. No entanto, para cada máquina Moore existe uma máquina Mealy equivalente e vice- versa.

As máquinas de Moore são a família mais simples de transdutores acabados .

Definição formal

Uma máquina de Moore é uma 6 tupla

(Q,eu,NO,B,δ,λ){\ displaystyle (Q, i, A, B, \ delta, \ lambda)}

feito de :

• um conjunto finito de estados  ;Q{\ displaystyle Q}
• um estado inicial , elemento de  ;eu{\ displaystyle i}Q{\ displaystyle Q}
• um conjunto finito , denominado alfabeto de entrada;NO{\ displaystyle A}
• um conjunto finito , denominado alfabeto de saída;B{\ displaystyle B}
• uma função de transição ;δ:Q×NO→Q{\ displaystyle \ delta: Q \ times A \ to Q}
• uma função de saída .λ:Q→B{\ displaystyle \ lambda: Q \ to B}

É conveniente observar o status por e o símbolo de saída por . A função de transição e a função de saída são estendidas às palavras de por indução, para e , por δ(q,no){\ displaystyle \ delta (q, a)}q⋅no{\ displaystyle q \ cdot a}λ(q⋅no){\ displaystyle \ lambda (q \ cdot a)}q⋆no{\ displaystyle q \ star a}NO∗{\ displaystyle A ^ {*}}C∈NO∗{\ displaystyle w \ in A ^ {*}}no∈NO{\ displaystyle a \ in A}

q⋅Cno=(q⋅C)⋅no,q⋆Cno=(q⋆C)((q⋅C)⋆no).{\ displaystyle q \ cdot wa = (q \ cdot w) \ cdot a, \ quad q \ star wa = (q \ star w) ((q \ cdot w) \ star a).}

Em outras palavras, a saída produzida pela palavra , lida do estado , é a palavra produzida pela palavra , lida do estado , seguida pela letra associada ao estado alcançado após a leitura . Cno{\ displaystyle wa}q{\ displaystyle q}C{\ displaystyle w}q{\ displaystyle q}q⋅Cno{\ displaystyle q \ cdot wa}Cno{\ displaystyle wa}

A função desempenhada pelo autômato de Moore é a aplicação definida por: f:NO∗→B∗{\ displaystyle f: A ^ {*} \ to B ^ {*}}

f(C)=eu⋆C{\ displaystyle f (w) = i \ star w}

É, portanto, a função que a uma palavra de , lida a partir do estado inicial , associa a palavra on obtida pela concatenação das letras associadas aos estados de chegada das transições percorridas. C{\ displaystyle w}NO∗{\ displaystyle A ^ {*}}eu{\ displaystyle i}B∗{\ displaystyle B ^ {*}}

Variantes

Às vezes, uma máquina de Moore tem um conjunto finito de estados terminais . A função executada é então restrita a palavras de linguagem racional no alfabeto de entrada reconhecido pelo autômato. A linguagem das palavras produzidas pela função é então uma linguagem racional . f{\ displaystyle f}f{\ displaystyle f}

Normalmente, a função de transição é total; quando é parcial, a ausência de transição resulta no bloqueio do PLC. δ:Q×NO→Q{\ displaystyle \ delta: Q \ times A \ to Q}

Exemplo

O exemplo acima tem quatro estados. A função de transição é parcialmente definida no estado Tomando como estado inicial, o PLC produz, para a palavra de entrada , a palavra de saída . A carta nunca é produzida porque não há transição terminando em . q0{\ displaystyle q_ {0}}zxzy{\ displaystyle zxzy}novsnovs{\ displaystyle acac}b{\ displaystyle b}q0{\ displaystyle q_ {0}}

Transformação no autômato de Mealy

A transformação de um autômato de Moore em um autômato de Mealy equivalente é muito simples. Acrescentamos a uma transição a carta de saída do estado de chegada. No exemplo, o resultado é o seguinte:

Um problema

Em seu artigo referenciado, Moore considera máquinas do tipo ( n  ; m  ; p ). Eles são autômatos com n estados, m símbolos de entrada e p símbolos de saída. Na seção Problemas adicionais no final de seu artigo, ele sugere estudar o seguinte problema: "Melhorando os limites dados nos Teoremas 8 e 9". O Teorema 8 é o seguinte:

Teorema 8  -  Dada uma máquina do tipo ( n  ; m  ; p ) tal que quaisquer dois de seus estados são distinguíveis, existe um experimento de comprimento que determina o estado no final do experimento. não(não-1)/2{\ displaystyle n (n-1) / 2}

Anatolii Alexevich Karatsuba resolveu o problema de Moore de melhorar o terminal acima, provando, em 1957, enquanto ele era um estudante na Faculdade de Mecânica da Universidade Estadual de Moscou Lomonosov , o seguinte resultado:

Teorema  -  Dada uma máquina do tipo ( n  ; m  ; p ) tal que quaisquer dois de seus estados são distinguíveis, há um experimento de comprimento que determina o estado no final do experimento. Além disso, esse limite é atingido. (não-1)(não-2)/2+1{\ displaystyle (n-1) (n-2) / 2 + 1}

Este resultado foi publicado em 1960.

Notas

1. (in) AA Karatsuba , "  Solução de um problema da teoria dos autômatos finitos  " , Usp. Mastro. Nauk , n o  15: 3,1960, p.  157–159.

• (fr) Edward F. Moore , “Gedanken-experiencias em máquinas sequenciais” , em C. Shannon e J. McCarthy (eds), Automata studies , Princeton, NJ, Princeton University Press, coll.  "Annals of estudos matemática" ( N O  34),1956, p.  129--153

• (en) / (de) Este artigo foi retirado parcial ou totalmente de artigos intitulados em inglês “  Moore machine  ” ( veja a lista de autores ) e em alemão “  Moore-Automat  ” ( veja a lista de autores ) .

Veja também

• Autômato acabado
• Mealy Machine
• Transdutor acabado

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">