Autômatos Finitos Determinísticos e Não Determinísticos

Autômatos Finitos Determinísticos e Não Determinísticos

Autômato Finito Determinístico

Autômato Finito Não-Determinístico

AFD X AFN

• Determinístico

Não determinístico

Autômato Finito Determinístico

– 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

alternativos

– Várias sequencias

possíveis

Definição:

Autômato Finito Determinístico

• 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:

Conclusão:

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:

1 - 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.

2 - 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

3 - 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.

Autômato Finito Determinístico

Seu funcionamento:

Autômato Finito Não-Determinístico

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 Não-Determinístico

Questão Fechada

Dado o AFN abaixo, diga qual cadeia é aceita.

Definição:

Autômato Finito Determinístico

Partes de um Autômato Finito Determinístico:

Autômato Finito Determinístico

Exemplo AFN:

Representação do AFD em Diagrama:

Transição: Representado por uma flecha ligando de um estado comum ao outro.

Transição

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.

Autômato Finito Determinístico

Estado Final: Representado com um círculo dentro do estado comum.

Estado Final

Funcionamento do autômato:

Autômato Finito Não Determinístico

• Fita: 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.

• Unidade de Controle: 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.

Estado comum: Representado com "q" e mais algum número. Obs: A notação "q" é utilizada por representar estado.

a) 0010, 0001100, 0011000

b) 00110, 101001, 000100

c) 0010010, 001010, 001000

d) 100100, 0010001010, 00100010

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.

Estado inicial: Representado com uma seta grande no círculo do estado comum.

Estado Inicial

Características:

Os AFNs não são mais expressivos do que os

AFDs

– São formalismos equivalentes

• Ambos reconhecem a mesma classe de

linguagens

– Linguagens Regulares (ou tipo 3)

Autômato Finito Não-Determinístico

Definição:

Autômato Finito Determinístico

Autômato Finito Determinístico (AFD), ou simplesmente autômato finito (M) é uma quíntupla:

Questão Fechada

Dado o AFN abaixo, diga qual cadeia é aceita.

a) 0010, 0001100, 0011000

b) 00110, 101001, 000100

c) 0010010, 001010, 001000

d) 100100, 0010001010, 00100010

Rafael Nunes Eulálio de Souza