FTC aula AFD intro

Prévia do material em texto

Introdução à Autômatos Finitos
Leonardo Reis
Departamento de Computação e Sistemas
Universidade Federal de Ouro Preto
Leonardo Reis (DECSI) FTC 1 / 7
Máquinas de Estados Finitos
máquinas abstratas que capturam as partes essenciais de máquinas
concretas
Leonardo Reis (DECSI) FTC 2 / 7
Quebra-Cabeça
Quais as informações relevantes?
Como estruturar as informações de modo a facilitar a obter a solução?
Leonardo Reis (DECSI) FTC 3 / 7
Noções Iniciais
Estado: fotografia dos elementos essenciais (informação)
Transição: movimento que leva de um estado a outro
Estado inicial: estado de partida
Estados finais: estados da configuração “desejada”
Leonardo Reis (DECSI) FTC 4 / 7
Configuração Instantânea
O que é preciso para saber se w = xy é reconhecida depois de terminar
de processar x?
Leonardo Reis (DECSI) FTC 5 / 7
Elevador de 3 Andares
Fica parado se não houver chamada
Fica no mesmo andar enquanto estiver sendo requisitado no mesmo
Dá prioridade para o andar do sentido que estiver se movimentando
Leonardo Reis (DECSI) FTC 6 / 7
Um Problema Matemático
Dada uma sequência de 0s e 1s, determinar se o número representado
por essa sequência é divisível por 6.
n x x0 x1 x%6 x0%6 x1%6
0 0 00 01 0 0 1
1 1 10 11 1 2 3
2 10 100 101 2 4 5
3 11 110 111 3 0 1
4 100 1000 1001 4 2 3
5 101 1010 1011 5 4 5
6 110 1100 1101 0 0 1
7 111 1110 1111 1 2 3
Leonardo Reis (DECSI) FTC 7 / 7