lista4-resp (1)

Prévia do material em texto

UNIVERSIDADE ESTADUAL DE MARINGÁ – UEM 
CENTRO DE TECNOLOGIA – CTC 
DEPARTAMENTO DE INFORMÁTICA – DIN 
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
PROFESSOR: YANDRE MALDONADO E GOMES DA COSTA 
 
Lista de Exercícios no 4 – Autômatos e Expressões Regulares 
 
1. Descreva Expressões Regulares equivalentes aos autômatos representados 
pelos diagramas descritos a seguir: 
 
a. 
 
 
 
 
 
 
 
b. 
 
 
 
 
 
 
 
 
2. Construa AFDs para as seguintes Expressões Regulares: 
a. ab(bb)*cc* 
 
 
 
 
 
 
 
 
 
 
 
 
 
S0 S2 S1 
b 
a 
a 
S3 
c d 
S0 S1 
a 
S4 
a 
S3 
b 
S2 
c d b 
a(aa)*bc*d 
a(cd)*ba(ba)* 
S0 S1 
a 
S2 
b 
S3 
b 
c 
S4 
c 
b 
b. cc*b*+ab*cc* 
 
 
 
 
 
 
 
 
 
 
c. bcc*(b+a)* 
 
 
 
 
 
 
 
3. Descreva a linguagem associada ao autômato descrito pela seguinte tabela 
de transição: 
 
A1 = < {a, b}, {S0, S1, S2, S3}, S0, δ, {S0, S2} > 
 
Com δ dada pela seguinte tabela: 
 a b 
S0 S1 S3 
S1 S2 S0 
S2 S3 S1 
S3 S0 S2 
 
 
 
 
 
 
 
 
 
 
 
L = { w ∈ {a, b}* | |w|a + |w|b = 2n ∧ n≥0 } 
ou 
L = {w ∈ {a, b}* | a soma das quantidades de símbolos a e de símbolos b é par} 
O diagrama não é obrigatório 
na resposta deste exercício. 
S0 
S3 S2 
S1 
a b b a 
a 
b 
b 
a 
S0 S1 
c 
S2 
b 
S3 
c 
S4 
c 
a 
b 
b c 
S0 S1 
b 
S2 
c 
c 
S3 
b, a 
b, a 
 
4. Dada a seguinte tabela de transição, encontre uma Expressão Regular 
equivalente e descreva um Autômato Finito Determinístico equivalente: 
 
A2 = < {0,1}, {S0, S1, S2, S3}, S0, δ, {S3} > 
 
Com δ dada pela seguinte tabela: 
 0 1 
S0 {S0, S1} {S0} 
S1 {S2} {S2} 
S2 {S3} ∅ 
S3 {S3} {S3} 
 
 
(0+1)*0(0+1)0(0+1)* 
 
 
 
 
 
 
 
 
S0 S01 
0 0 
1 
0 
1 
0 
1 
1 
S012 
S02 
S0123 
0 
S013 
S023 
1 
0 
1 
0 
S03 
1 
1 
0