Autômatos Finitos Determinísticos e Não Determinísticos by Rafael Nunes on Prezi
Transcript of Autômatos Finitos Determinísticos e Não Determinísticos
O autômato finito ou (máquina de estados finitos) é o primeiro modelo computacional de definição de linguagens que são definidas por mecanismo de reconhecimento, que pode ser encarado como um teste aplicado a cada caractere da palavra (w).
A linguagem reconhecida pelo autômato finito é constituída por todas as palavras que passem no teste. Este teste é aplicado de forma incremental, percorrendo os símbolos da palavra um a um a partir do seu inicio, e a decisão final só surge após o percurso completo da palavra, conferindo a qualidade computacional dos autômatos finitos.
Um Autômato Finito Determinístico, ou simplesmente autômato finito, pode ser vista como uma máquina composta basicamente por três partes:
Dispositivo de entrada que contém a informação a ser processada. A fita é finita à esquerda e à direita. É dividida em células onde cada uma armazena um símbolo. Os símbolos pertencem a um alfabeto de entrada ( ∑ ). Não é possível gravar sobre a fita. Não existe memória auxiliar. Inicialmente a palavra a ser processada, isto é, a informação de entrada ocupa toda a fita.
Reflete o estado corrente da máquina. Possui uma unidade de leitura (cabeça de leitura, que acessa uma unidade da fita de cada vez. Pode assumir um número finito e pré-definido de estados. Após cada leitura a cabeça move-se uma célula para a direita.
Programa ou Função de Transição:
Função que comanda as leituras e define o estado da máquina. Dependendo do estado corrente e do símbolo lido determina o novo estado do autômato. Usa-se o conceito de estado para armazenar as informações necessárias à determinação do próximo estado, uma vez que não há memória auxiliar.
O processamento de um autômato finito M para uma palavra de entrada w consiste na sucessiva aplicação da Função de Transição para cada símbolo de w, da esquerda para direita, até ocorrer uma condição de parada.
Exemplo: Autômato Finito
O autômato finito M1 = ({a, b}, {q0, q1, q2, qf}, δ1, q0, {qf}), onde δ1 é representada pela tabela de transição de estados, reconhece a linguagem.
L1 = {w | w possui aa ou bb como subpalavra}
Autômato Finito Determinístico (AFD), ou simplesmente autômato finito (M) é uma quíntupla:
Rafael Nunes Eulálio de Souza
Partes de um Autômato Finito Determinístico:
Estado comum
Representação do AFD em Diagrama:
Representado por uma flecha ligando de um estado comum ao outro.
Representado com um círculo dentro do estado comum.
Representado com "q" e mais algum número. Obs: A notação "q" é utilizada por representar estado.
Representado com uma seta grande no círculo do estado comum.
O algoritmo apresentado usa os estados q1 e q2 para "memorizar" o símbolo anterior. Assim q1 representa "o símbolo anterior é a" e q2 representa "o símbolo anterior é b". Após identificar dois "aa" ou dois "bb" consecutivos o autômato assume o estado qf (final) e varre o sufixo da palavra de entrada sem qualquer controle lógico, somente para terminar o processamento. A figura abaixo ilustra o processamento do autômato finito M1 para a palavra de entrada w = abba, a qual é aceita.
Funcionamento do autômato:
Note-se que um autômato finito sempre para ao processar qualquer entrada, pois como toda palavra é finita e como um novo símbolo de entrada é lido a cada aplicação da função programa, não existe a possibilidade de ciclo (loop) infinito. A parada do processamento pode ocorrer de duas maneiras: aceitando ou rejeitando uma entrada w. As condições de parada são as seguintes:
Após processar o último símbolo da fita o autômato finito assume um estado final. O autômato para e a entrada w é aceita.
Após processar o último símbolo da fita, o autômato finito assume um estado não-final. O autômato para e a entrada w é rejeitada
A função programa é indefinida para o argumento (estado corrente e símbolo lido). O autômato para e a entrada w é rejeitada.
Para definir formalmente o comportamento de um autômato finito (ou seja, dar semântica à sintaxe de um autômato finito) é necessário estender a definição da função programa, usando como argumento um estado e uma palavra.
Exemplo AFN:
– Transições bem definidas
– Função de transição leva a um único estado
– Sequência de estados é única para cada palavra
– Transições ambíguas
– Função de transição leva
a vários estados
– Várias sequencias
AFD X AFN
Os AFNs não são mais expressivos do que os
– São formalismos equivalentes
• Ambos reconhecem a mesma classe de
– Linguagens Regulares (ou tipo 3)
Um AFN, similarmente a um AFD, lê uma cadeia de símbolos de entrada. Para cada símbolo da entrada há uma transição para um novo estado, até que todos os símbolos de entrada sejam lidos, porém existe pelo menos um estado tal que ao ler um mesmo símbolo há mais de uma possibilidade de estado destino. Assim, o próximo estado é um elemento do conjunto das partes dos estados.