Solução Exercícios Autômato Finito Determinístico (AFD)

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 2 – Autômato Finito Determinístico (AFD) 
 
1. Descreva a definição de AFD. 
 
Um AFD é uma quíntupla <Σ, S, S0, δ, F>, onde: 
� Σ é o alfabeto de entrada; 
� S é um conjunto finito não vazio de estados; 
� S0 é o estado inicial, S0 ∈ S ; 
� δ é a função de transição de estados, definida δ: S x Σ → S ; 
� F é o conjunto de estados finais, F⊆ S . 
 
 
2. Dado o alfabeto ∑ = {a,b}, construa AFDs para as seguintes linguagens: 
 
a) {b(ab)nb | n≥0} 
 
 
 
 
 
 
 
 
b) { banba | n≥0} 
 
 
 
 
 
 
 
 
 
 
 
 
 
S0 S1 
b 
S3 
b 
S2 
a b 
S0 S1 
b 
S2 
b 
a 
S3 
a 
c) {ambn | m+n é par} 
 
 
 
 
 
 
 
 
d) {abmba(ab)n | m, n ≥0} 
 
 
 
 
 
 
 
 
 
3. Seja ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, construa AFDs para as seguintes 
linguagens: 
 
a) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro par} 
 
 
 
 
 
 
 
 
b) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro 
divisível por 5} 
 
 
 
 
 
 
 
 
 
 
 
S0 S1 
a 
S2 
b 
S3 
b b a 
b 
S0 S1 
a 
S2 
b 
S4 
a 
b 
S3 
a 
b 
S0 S1 
0, 2, 4, 6, 8 0, 2, 4, 6, 8 
1, 3, 5, 7, 9 
1, 3, 5, 7, 9 
S0 S1 
0, 5 0, 5 
1, 2, 3, 4, 6, 7, 8, 9 
1, 2, 3, 4, 6, 7, 8, 9 
 
 
c) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro ímpar} 
 
 
 
 
 
 
 
 
4. Descreva um algoritmo de um AFD. 
 
Início 
 Estado Atual ← Estado Inicial; 
 Para I variar do Símbolo inicial da fita até o símbolo final 
 Faça Se Existe δ (Estado Atual, I) 
 Então Estado Atual ← δ (Estado Atual, I); 
 Senão REJEITA; 
 Se Estado Atual é estado final 
 Então ACEITA; 
 Senão REJEITA; 
Fim. 
 
 
5. Qual é a linguagem definida pelo seguinte autômato? 
 
 
 
 
 
 
 
 
 
 
 
 
L = { w ∈ {a, b}* | |w|a = 2n+1 ∧ |w|b = 2m+1 ∧ n, m≥0 } 
 
ou 
 
L = { w ∈ {a, b}* | a quantidade de símbolos ‘a’ e a quantidade de símbolos ‘b’ 
em w é ímpar} 
S0 
S2 Sf 
S1 
b b b b 
a 
a 
a 
a 
S0 S1 
1, 3, 5, 7, 9 1, 3, 5, 7, 9 
 
0, 2, 4, 6, 8 
0, 2, 4, 6, 8