Tema 02 - AFDs Computadores de Funções - ATIVIDADE EM AULA 2020 1

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
TEMA 2: AFD's como Computadores de Funções - 
 
ATIVIDADES PARA RESOLUÇÃO EM SALA DE AULA 
Após estudar o MATERIAL DE APOIO do tema AFD's como Computadores de Funções, resolva os exercícios a 
seguir. Nota: esta atividade será realizada em sala de aula, e valerá pontuação para a avaliação. 
PROBLEMAS 
I Resolva os exercícios abaixo, extraídos do MATERIAL DE APOIO AO ESTUDO. 
12) Seja a Máquina de Estado Finito representada pela tabela a seguir, onde I = { a, b, c } e O = { 0, 1 }. 
Estado 
atual 
Próximo estado 
Saída entrada atual 
a b c 
e0 e0 e0 e1 0 
e1 e2 e0 e1 0 
e2 e2 e1 e0 1 
a) Desenhe o seu grafo de estados correspondente 
b) Calcule as sequências de saída para as sequências de 
entrada a seguir, lidas da esquerda para a direita: 
abcabc 
c) Enumere TODAS as sequências de entrada possíveis que 
produzam as seguintes saídas: 
010001 001010 
13) Seja a Máquina de Estado Finito representada pelo grafo a seguir, onde I = { 0, 1 } e O = { 0, 1 }. 
e0 / 1
0, 1
0
e2 / 1
e1 / 0
1
1
0
 
 
b) Calcule a sequência de saída para a sequência de 
entrada a seguir, lida da esquerda para a direita: 
011101 
14) Para o AFD abaixo, onde I = { 0, 1 } e O = { a, b }: 
a) Complete o seu grafo de estados, sabendo 
que a sequência de entrada 111 gera a 
saída abba. 
b) Enumere TODAS as sequências de entrada 
que geram a saída abbb. 
e0/ e1/
e2/