1. FinalidadeDefinidas na teoria dos automatos e depois na teoria da computação, tem as seguintes finalidades . Tradutores ou Automatos Finitos com saida Para cada entrada existem duas saidas possiveis. Uma para sentenças validas e outras para sentenças invalidas da linguagem em questão. Ambas devem ser geradas a partir de gramaticas regulares. As saidas podem estar associadas a: transição ou estado . Dependeendo da associação existem 2 tipos de máquinas: Mealy e Moore. Com uma entrada vazia a Máquina de Mealy não gera saida pois não executa nenhuma transição ( a saida esta associada a transição). Um exemplo de aplicação é o projeto de dialogo entre um programa e o seu usuário. Este dialogo pode se comandado pelo usuario ou pelo programa. A saiada depende das entradas e do estado anterior A Máquina de Moore gera a palavra correspondente ao estado inicial (a saida esta associada ao estado). Um exemplo de aplicação é o analisador léxico de um compilador. A saida depende somente dos estados anteriores No caso de entrada vazia as duas máquinas não são equivalentes caso contrario (entrada não vazia) as máquinas são equivalentes ou seja uma simula a outra. Aplicações com enfase na WWW : Hipertexto e hipemidia; animação quadro-a-quadro. Reconhecedores de linguagem ou Automatos Finitos. Entradas são simbolos. Ações não são utilizadas Tem 2 tipos: Automato finito deterministico para cada entrada há exatamente uma transação para cada entrada possivel. Automata não deterministico - pode ter nenhuma ou mais de uma transação de um determinado estado para uma entrada possivel 2. Elementos de um automata finito Estado inicial - estado em o problema se encontra quando começa a ser resolvido Estado final - estado em que o problema se encontra quando começa a ser resolvido ou chegou-se a um estado em que não há saida. Estados -armazena informações sôbre o passado. Armazena as mudanças desde a entrada em um estado até o momento presente. Representado por um número circulado. Funcionamento - um automata finito funciona com a entrada de uma cadeia de letras. Essa cadeia é lida letra por letra até a ultima letra da cadeia. O inicio se dá pela escolha do estado inicial. As letras lidas indicam a sequência de estados a ser seguida. A sequência termina quando a última letra for lida. Entrada - cadeia de caracteres Saidas - podem se associar a: transições - maquina de Mealy estados - maquina de Moore Não pode ser lida ou seja não pode ser usada como memória auxiliar. Regras de transição -indica uma mudança de estado. É descrita por uma condição que precisa ser realizada para que a transiçaõ ocorra. Representa seta entre estados. Seja o alfabeto {a b} as regras de transição são: regra 1. Do estado x e entrada a, vá para o estado y. regra 2. Do esatdo x e entrada b, vá para o estado z regra 3. Do estado y e entrada a, vá para o estado x. regra 4. Do esatdo y e entrada b, vá para o estado x. regra 5. Do estado z e qualquer entrada, continue no estado z. Ações - é a descrição de uma atividade que deve ser realizada em determinado momento. Ação de entrada (no estado) - executa a ação quando entra no estado. Ação de saida : executa ações quando sai do estado. 3. Representação graficaNa forma de grafos dirigidos das regras descritas no item anterior. Na forma de tabelas de transição (estado x entrada) 4. Definição matemáticaÉ uma quintupla AF=(E,A,I,F,T) E: conjunto finito de estados; A: um alfabeto; I: estado inicial; F: conjunto de estados finais; T: função de transição de estado T(E1, Xk) = Ej => indica para cada estado e cada letra do alfabeto a qual o estado deve seguir. 5. Autômatos finitos x Expressões RegularesUm automato pode ser abordado de 2 maneiras: A partir de uma linguagem (expr. regular) constroi-se uma máquina de estado para ela ou a partir de uma máquina de estado, deduz-se a linguagem
