2.1 Autômatos Determinísticos (AFDs)
Autômatos Finitos (AF's)
[editar | editar código-fonte]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
[editar | editar código-fonte]É 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
[editar | editar código-fonte]É 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:
[editar | editar código-fonte]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.