ListaExercicios_2

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO 
CENTRO DE CIÊNCIAS AGRÁRIAS – CCA/ UFES 
Departamento de Engenharia Rural 
Lista de exercícios 2 
Disciplina: Computabilidade e Complexidade 
Professora: Juliana Pinheiro Campos 
Data: 09/09/2010 
Assuntos: Introdução (alfabeto, cadeias, strings, etc), AFD’s e AFN’s, Linguagens regulares, Expressões 
regulares 
 
1) Faça os seguintes exercícios do livro-texto (Introdução à Teoria da Computação do Michael 
Sipser) que se encontram a partir da página 79. 
 
OBS: as figuras estão numeradas no livro após todos os exercícios. 
 
 1.4: b, d, e, f, g, h, i, n. 
 
 1.5: d, e, g. 
 
 1.6: a 
 
 1.7: a 
 
 1.8: a 
 
 1.9 
 
 1.13: b, c, d, e, f, g, h, i, k, n. 
 
 1.14 
 
 1.15 
 
 1.16 
 
 
2) Sabendo que o alfabeto é {0,1}, dê o AFD mínimo que reconhece a seguinte linguagem: 
 
 {w | w contém um número par de 0's ou exatamente dois 1's}