2.1 Autômatos Determinísticos (AFDs)

Autômatos Finitos (AF's)

Vamos ver dois modelos que podem ser vistos como propostas de definições de algoritmo (ou

modelos de computação), apesar de, historicamente, não terem surgido com esse propósito!

Estes modelos de computação são baseados no conceito de máquinas de estados, que explicamos a seguir.

Diagramas (ou Máquinas) de Estados

É um tipo de diagrama usado na Computação para representar o comportamento de algum sis-

tema.

Eles têm estados, que representam cada possível “situação atual” do sistema. Um estado pode

estar associado também a alguma saída do sistema.

• São representados visualmente com círculos

Existe um estado especial chamado estado inicial do diagrama

• Será representado com um círculo com uma seta vinda “do nada”.

Transições (mudanças) entre estados dependem das entradas do sistema

• São representadas com setas

Para projetar o sistema adequadamente, é preciso pensar bem:

(1) no significado de cada estado;

(2) para qual estado mudar a cada entrada.

Possíveis aplicações dos diagramas de estados:

• Projetar um personagem de um game
• Projetos de agentes inteligentes em geral
• Projetar um elevador de um único botão, para um prédio de 3 andares
• Projetar circuitos digitais em geral

Ideia básica dos Autômatos Finitos: usar diagramas de estados para representar um algoritmo

para resolver problemas ou representar linguagens.

Veremos dois tipos: os determinísticos e os

não-determinísticos.

Autômatos Finitos Determinísticos

É baseado no conceito de diagrama de estados. As entradas da máquina de estados são os sucessivos símbolos da cadeia de entrada.

• Um símbolo por vez é lido da esquerda para a direita

• O símbolo “da vez” determina cada transição (mudança de estado)

Para comparar, um AFD é quase como uma MT mais limitada que, em toda transição, move

para direita e para/interrompe quando acabam os símbolos da entrada.

Podemos dizer que há dois tipos principais de estados

• Estados de aceitação, representados com círculos duplos
• Estados de “não-aceitação”, representados com um círculo simples

Observação: o estado inicial pode ser de qualquer um desses tipos.

Dizemos que um AFD X aceita uma cadeia w quando:

• o X leu toda1 a cadeia w e o Ao final (após ler a cadeia), termina em um estado de aceitação

Consideramos que X rejeita a cadeia w, caso contrário.

Podemos dizer que AFD representa ou decide uma linguagem aceitando as cadeias que fazem

parte dela e rejeitando as cadeias que não fazem. Ou podemos dizer que ele resolve ou decide

um problema de decisão quando dá a resposta aceita ou rejeita corretamente para toda entrada

possível.

Para algum autômato finito X, referenciamos a linguagem que ele decide como L(X), que pode

ser lido como “a linguagem que o autômato X representa”.

Exemplos contidos no link abaixo:

https://classroom.google.com/u/0/w/NTM1NDgwNjAwNzYz/t/all

• Exemplo: considerando o alfabeto {0,1}, construir o AFD M1, tal que:

L(M1) = { w | w tem uma quantidade par de 0s }

= { , 00, 100, 010, 001, 01110, 10101, 0000, 001010, ...}

• Exercício: considerando o alfabeto {0,1}, construir o AFD M2, tal que:

L(M2) = { w | w tem uma quantidade de 0s múltipla de 3 }

= { , 11, 000, 0100, 1, 011001, 00100010, ...}

dica: pense bem nos significados de cada estado

• Exemplo: considerando o alfabeto {a,b}, construir o AFD M3, tal que:

L(M3) = { w | w tem a subcadeia aa }

Exercício: considerando o alfabeto {a,b}, construir o AFD M4, tal que:

L(M4) = { w | w termina em ba }

* dica: pense bem nos significados de cada estado

Depois desta apresentação inicial, veremos a visão mais formal/matemática dos AFD's nas próximas seções.