Máquinas de Moore e de Mealy (1)

Prévia do material em texto

<p>Máquinas de</p><p>Moore e de Mealy</p><p>AUTÔMATO FINITO COM SAÍDA</p><p>Os autômatos finitos com saída,são dispositivos que geram apenas uma saída são conhecidos como tradutores, pois a cada fita de entrada que lhes é fornecida, produzem uma nova fita de acordo, com um novo padrão de símbolos.</p><p>Este tipo, por sua vez, não possui estados finais, sendo uma das principais diferenças entre o mesmo e um autômato finito sem saída.</p><p>A máquina de Mealy</p><p>A máquina de Mealy é um autômato finito, cuja saída está diretamente ligada às transições realizadas pelo mesmo, se considerarmos o tamanho da fita de entrada com n unidades, o tamanho da fita de saída será igual.</p><p>É representado por uma 6-upla M = (Σ, Q, δ, q0, F, ∆).</p><p>Σ: alfabeto de símbolos de entrada;</p><p>Q: conjunto de estados possíveis do autômato, o qual é finito;</p><p>δ: Q x Σ → Q x ∆* função programa ou função de transição, a qual é uma função parcial que, dependendo do estado corrente e do símbolo lido, determina o novo estado do autômato e a saída gerada;</p><p>q0: estado inicial tal que q0 é elemento de Q;</p><p>F: conjunto de estados finais tal que F está contido em Q;</p><p>∆: alfabeto de símbolos de saída”</p><p>a	b	a	a	b</p><p>1	0	1	1	0</p><p>δ	a	b</p><p>q0	q0	q1</p><p>q1	q2	q3</p><p>q2	q3	----</p><p>q3	q1	q2</p><p>Exemplo de Mealy</p><p>Entrada</p><p>Saída</p><p>Tabela</p><p>Máquina de Moore</p><p>A Máquina de Moore é um autômato finito assim como o modelo de Mealy, porém a saída está ligada diretamente aos estados ao considerarmos o tamanho da fita de saída desse modelo.</p><p>É representada por uma 7-upla M = (Σ, Q, δ, q0, F, ∆, δS)</p><p>Σ: alfabeto de símbolos de entrada;</p><p>Q: conjunto de estados possíveis do autômato, o qual é finito;</p><p>δ: Q x Σ → Q função programa ou função de transição, a qual é uma função parcial que, dependendo do estado corrente e do símbolo lido, determina o novo estado do autômato;</p><p>q0: estado inicial tal que q0 é elemento de Q;</p><p>F: conjunto de estados finais tal que F está contido em Q;</p><p>∆: alfabeto de símbolos de saída;</p><p>δS: Q → ∆* função de saída, a qual é uma função total que determina a geração de uma palavra de saída para cada estrado</p><p>Exemplo de Moore</p><p>b	a	b	a	b</p><p>Entrada</p><p>Saída</p><p>1	0	1	0	1</p><p>δ	a	b</p><p>q0	q1	q0</p><p>q1	----	q2</p><p>q2	q1	q2</p><p>Tabela</p><p>Equivalência das Máquina de Moore e Mealy</p><p>As máquinas de Moore e Mealy, apesar de serem autômatos distintos, são equivalentes pois há a possibilidade de conversão de um modelo para o outro.</p><p>Quando realizado o processo de conversão do modelo de Mealy para Moore pode acarretar na formação de novos estados, no processo contrário será mantido o mesmo número de estados.</p><p>Exemplos de Aplicação</p><p>Modelo de Moore</p><p>Temos o desenvolvimento de Analisadores Léxicos de compiladores ou tradutores de linguagens em geral.</p><p>Modelo de Mealy</p><p>Temos como exemplo a utilização na criação de circuitos lógicos, também é utilizado em projetos de diálogos entre usuário e computador.</p><p>image1.png</p><p>image2.png</p>