Tema 03 - AFDs Reconhecedores de Linguagens - EXERCÍCIOS

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
TEMA 3: AFD’s para Reconhecimento de Linguagens 
 
EXERCÍCIOS 
Após estudar o MATERIAL DE APOIO do tema AFD's para Reconhecimento de Linguagens, resolva os exercícios a 
seguir. 
1. Para o AFD abaixo, enumere todas as sequências de comprimento menor ou igual a QUATRO, indicando se 
cada uma é aceita (reconhecida) ou rejeitada (não aceita) pelo AFD em questão. 
e0
0
1
1
0
1
e1 e2
0
1
e4e3 0
0
1
 
• Reconhecidas: 
 
 
 
 
• Não aceitas: 
 
 
 
 
 
2. Para cada AFD reconhecedor M abaixo, caracterize corretamente, em português, a linguagem L(M). 
Não precisa indicar qual é o alfabeto de entrada; assuma que ele já está implícito – veja o exemplo. 
a) 
a,b
a,b
e0 e1
 
Resposta: 
Sequências de comprimento par. 
 
 
b) 
e0
0
1
1
0
1
e1 e2
0
1
e4e3 0
0
1
 
c) 
1
1
e0
0,1
e1
0
0
e2
 
 
 
d) 
e4
0
e1
e3
1
1
e2
0
0
1 0
1
1
0
e0
 
e) 
a
b
e1
e2
a,b
a,b
e0
 
 
 
3. Quantas sequências INICIADAS por b e de COMPRIMENTO SETE são reconhecidas pelo AFD da questão 2 e)? 
JUSTIFIQUE SUA RESPOSTA! 
 
 
4. Para cada AFD reconhecedor M abaixo, descreva CORRETAMENTE em português a linguagem L(M). 
Assumir que o alfabeto de entrada já está implícito, como no item c). 
a) 
e3
0
1
0
1
0,1
e1
e0
e2
0
1
 
b) 
0
1,0
e2
1
e0
0
1
e1
 
 
c) 
1
0,1
e2
0
e0
e1
0,1
 
d) 
a
b
b
e1
a
e0
 
 
e) 
0
1,0
1
e0
0
1
e1
e2