eventos
topico
nomeAutomata finito
tituloAutomata finito
descritorAutomata finito
leadSão máquinas que funcionam sozinhas em resposta a entradas de um dado. É uma outra forma de representação de linguagens formais.
linkrepresentação tabular  visao da eletronica  wikipedia ferramenta   Domain-Specific Languages
origemAutomataFinito.xml
referencia  AutomataFinito
topico
tituloFinalidade
descDefinidas 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


topico
tituloElementos de um automata finito
desc
  • 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. 
topico
tituloRepresentação grafica
descNa forma de grafos dirigidos das regras descritas no item anterior.



Na forma de tabelas de transição (estado x entrada)



topico
tituloDefinição matemática
descÉ 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.

topico
tituloAutômatos finitos x Expressões Regulares
descUm 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