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
b
S0
S1
S3
a
b
S2
b) { banba | n≥0}
a
b
S0
b
S1
a
S2
S3
c) {ambn | m+n é par}
a
b
S0
S1
S2
a
b
b
b
S3
d) {abmba(ab)n | m, n ≥0}
b
a
S0
b
S1
a
S2
S3
a
b
S4
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}
0, 2, 4, 6, 8
S0
0, 2, 4, 6, 8
S1
1, 3, 5, 7, 9
1, 3, 5, 7, 9
b) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro
divisível por 5}
0, 5
S0
0, 5
S1
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}
1, 3, 5, 7, 9
S0
1, 3, 5, 7, 9
S1
0, 2, 4, 6, 8
0, 2, 4, 6, 8
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?
a
S0
S1
a
b
b
b
b
a
S2
Sf
a
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}