Ciencia da computacao

Autˆ matos com Sa´da - M´ quina de Mealy e M´ quina de o ı a a Moore
MAT A50 - Linguagens Formais e Autˆ matos o

1. Introducao ¸˜
´ ` o O conceito b´ sico de autˆ mato finito e restrito, pois sua sa´da se limita a l´ gica bin´ ria a o ı a aceita/rejeita. Sem alterar a clase das linguagens reconhecidas, pode-se estender a definicao de ¸˜ Autˆ matos Finitos para gerar uma palavra de sa´da. o ı ` A sa´da pode estar associada as transicoes (M´ quina de Mealy) ou aos estados ı ¸˜ a ´ (M´ quina de Moore). Em ambos, a sa´da n˜ o pode ser lida e e definida da seguinte a ı a maneira: • • • • possui um alfabeto pr´ prio (Alfabeto de Sa´da), que pode ser igual ao de entrada; o ı a sa´da e armazenada em uma fita diferente da de entrada; ı ´ a cabeca da fita se move 1 c´ lula para a direita para cada s´mbolo gravado; ¸ e ı ´ o resultado do processamento e o estado final mais a informacao contida na fita de ¸˜ sa´da. ı

2. M´ quina de Mealy a
´ Definicao: Uma m´ quina de Mealy e um Autˆ mato Finito Determin´stico (AFD) com ¸˜ a o ı ` ´ sa´das associadas as transicoes e e representada por uma 6-upla: ı ¸˜ M = (Σ, Q, δ, q0, F, ∆) • • • • • • Σ - Alfabeto de Entrada; Q - Conjunto de estados; δ - Funcao de transicao (δ: QxΣ → Qx∆*); ¸˜ ¸˜ q0 - Estado inicial; F - Estados finais; ∆ - Alfabeto de Sa´da. ı

Exemplo: Fazer uma M´ quina de Mealy que leia uma cadeia de 0’s e 1’s e produza a uma sa´da trocando os caracteres da entrada (0’s por 1’s e 1’s por 0’s) - Figura 1. ı

´ Figure 1. Maquina de Mealy

Escrever a palavra vazia n˜ o move a cabeca da fita de sa´da. Uma M´ quina de a ¸ ı a Mealy que gera apenas sa´das vazias se comporta como um AFD. ı

3. M´ quina de Moore a
´ Definicao: Uma m´ quina de Moore e um AFD com sa´das associadas aos estados repre¸˜ a ı sentada por uma 7-upla: M = (Σ, Q, δ, q0, F, ∆, δs) • • • • • • • Σ - Alfabeto de Entrada; Q - Conjunto de estados; δ - Funcao de transicao (δ: QxΣ → Q); ¸˜ ¸˜ q0 - Estado inicial; F - Estados finais; ∆ - Alfabeto de Sa´da;