Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

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

No description
by

Rafael Nunes

on 9 June 2015

Comments (0)

Please log in to add your comment.

Report abuse

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

Autômato Finito Determinístico
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:
Autômato Finito 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.
Autômato Finito 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 Determinístico
Autômato Finito Determinístico (AFD), ou simplesmente autômato finito (M) é uma quíntupla:

Autômato Finito Determinístico
Autômatos Finitos Determinísticos e Não Determinísticos
Rafael Nunes Eulálio de Souza
Definição:
Partes de um Autômato Finito Determinístico:
Transição
Estado Final
Estado comum
Estado Inicial
Representação do AFD em Diagrama:
Transição:
Representado por uma flecha ligando de um estado comum ao outro.
Estado Final:
Representado com um círculo dentro do estado comum.
Estado comum:
Representado com "q" e mais algum número. Obs: A notação "q" é utilizada por representar estado.
Estado inicial:
Representado com uma seta grande no círculo do estado comum.
Seu funcionamento:
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.
Autômato Finito Determinístico
Autômato Finito Determinístico
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:

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.

Conclusão:
Autômato Finito Não-Determinístico
Definição:
Autômato Finito Não-Determinístico
Exemplo AFN:
Autômato Finito Não-Determinístico
– Transições bem definidas
– Função de transição leva a um único estado
– Sequência de estados é única para cada palavra
Autômato Finito Não-Determinístico
Determinístico
– Transições ambíguas
– Função de transição leva
a vários estados
alternativos
– Várias sequencias
possíveis
Não determinístico
AFD X AFN
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
Características:
Definiçã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.
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
Questão Fechada
a) 0010, 0001100, 0011000

b) 00110, 101001, 000100

c) 0010010, 001010, 001000

d) 100100, 0010001010, 00100010
Dado o AFN abaixo, diga qual cadeia é aceita.
Full transcript