Tema 04 - Construção de AFDs Reconhecedores - TEXTO DE APOIO

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
TEMA 4: Construção de AFD’s Reconhecedores 
 
TEXTO PARA APOIO AO ESTUDO 
4.1 A construção de AFD’s Reconhecedores de Linguagens 
Neste tema vamos estudar a construção de um AFD reconhecedor M, a partir da especificação da linguagem L(M). 
Consideraremos implicitamente o alfabeto de entrada I = { a, b }, ou então, quando for o caso, o alfabeto I = { 0, 1 }. 
Recapitulando, para toda sequência α ∈ I*, o AFD M deverá: 
 Terminar em um estado final, se α ∈ L(M); e 
 Terminar em um estado não final, α ∉ L(M) 
4.2 Construindo AFD’s reconhecedores 
Vamos examinar vários exemplos de construção de AFD’s, a partir da especificação de L(M). Primeiro, enumeramos 
algumas sequências que serão aceitas e algumas das rejeitadas por M. Depois vamos considerar aspectos da 
estrutura de cada autômato. 
Um primeiro aspecto a ser considerado é quanto ao estado inicial e0. Se a entrada lida for a sequência vazia (α = λ), 
então o processamento de M logo terminará no próprio e0. Assim, devemos ter: 
 Quando λ ∈ L(M) ⇒ e0 deverá ser um estado final; e 
 Quando λ ∉ L(M) ⇒ e0 deverá ser um estado não final. 
a) I = { a, b }. L(M) = { α ∈ I* | α é iniciada pelo símbolo a } 
 Algumas sequências: α ∈ L(M) ⇒ a, aa, ab, aaa, aab, aba, abb, aaaa, aaab, … 
 α ∉ L(M) ⇒ λ, b, ba, bb, baa, bab, bba, bbb, baaa, baab, … 
Como λ ∉ L(M), o estado e0 é não final. Se o primeiro símbolo for a, a função próximo estado δ deve promover a 
transição a um estado final, que chamaremos e1. Ou seja: δ(e0,a) = e1. Veja o AFD abaixo, com a função δ à direita. 
a
e0
e2 a,b
b
a,be1
 
Função de transição δ(e,i) 
δ(e0,a) = e1 δ(e1,a) = e1 δ(e2,a) = e2 
δ(e0,b) = e2 δ(e1,b) = e1 δ(e2,b) = e2 
Observemos alguns aspectos na construção do AFD acima: 
 Estando M em e1, os demais símbolos lidos não afetam o reconhecimento ⇒ M continua em e1; 
 Se o primeiro símbolo for b, o AFD não poderá ficar em e0 (veja que a sequência ba seria reconhecida); 
 Estando M em e2, outros símbolos lidos não afetam o não reconhecimento ⇒ M continua em e2. 
b) I = { a, b }. L(M) = { α ∈ I* | α é finalizada pelo símbolo a } 
 Algumas sequências: α ∈ L(M) ⇒ a, aa, ba, aaa, aba, baa, bba, aaaa, aaba, … 
 α ∉ L(M) ⇒ λ, b, ab, bb, aab, abb, bab, bbb, aaab, aabb, … 
Como λ ∉ L(M), e0 é não final. Sempre que um a for lido, δ deve promover a transição a um estado final – que 
chamaremos e1; e para todo b for lido, δ deve promover a transição a um estado não final. Veja o AFD abaixo: 
a
b
e0b ae1
 
c) I = { a, b }. L(M) = { α ∈ I* | α é iniciada por DOIS símbolos iguais } 
 Algumas sequências: α ∈ L(M) ⇒ aa, bb, aaa, aab, bba, bbb, aaaa, aaab, aaba, aabb, bbaa, bbab, … 
 α ∉ L(M) ⇒ λ, a, b, ab, ba, aba, abb, baa, bab, abaa, abab, abba, abbb, baaa, … 
Veja o AFD abaixo: 
e0
b
e2
e1
a
a,be4
a
a,b e3
b
a
b
 
Observemos alguns aspectos na construção do AFD acima: 
 Os dois símbolos iniciais são distintos ⇒ M pode ir ao mesmo estado e3 em ambos os casos – ab ou ba; 
 Os dois símbolos iniciais são idênticos ⇒ M pode ir ao mesmo estado e4 em ambos os casos – aa ou bb. 
d) I = { a, b }. L(M) = { α ∈ I* | α é finalizada com DOIS símbolos iguais } 
 Algumas sequências: α ∈ L(M) ⇒ aa, bb, aaa, abb, baa, bbb, aaaa, aabb, abaa, abbb, baaa, babb, … 
 α ∉ L(M) ⇒ λ, a, b, ab, ba, aab, aba, bab, bba, aaab, aaba, abab, abba, baab, … 
Tente construir um AFD reconhecedor para L(M), e confira a sua resposta no gabarito. Teste seu AFD com algumas 
das sequências acima, sempre observando se o processamento levou a um estado coerente. Em especial, teste com 
as sequências: λ, a, b, aa, aaa, aab, aabb, abb, abba, abbaa, abaa, babb, dentre outras. 
e) I = { a, b }. L(M) = { α ∈ I* | α tem comprimento par } 
 Algumas sequências: α ∈ L(M) ⇒ λ, aa, ab, ba, bb, aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, … 
 α ∉ L(M) ⇒ a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, aaaab, … 
Observe que |λ| = 0, que é par. Assim, λ ∈ L(M), e e0 é estado final. Veja o AFD abaixo, comentado a seguir: 
a,b
a,b
e0 e1
 
 Qualquer que seja o 1º símbolo lido, o comprimento passa a ser ímpar, e M vai para o estado não final e1. 
 Qualquer que seja o 2º símbolo lido, o comprimento passa a ser par, e M “volta” ao estado final e0. 
 O processamento segue a cada símbolo lido, alternando o estado atual de M entre e0 e e1. 
f) I = { a, b }. L(M) = { α ∈ I* | α contem um número par de ocorrências do símbolo a } 
 Algumas sequências: α ∈ L(M) ⇒ λ, b, bb, bbb, bbbb, …, aa, aab, aba, baa, aaaa, aabb, abab, abba, … 
 α ∉ L(M) ⇒ a, ab, ba, aaa, abb, bab, bba, abbb, aaab, aaba, abaa, abbb, baaa, … 
Observe que λ ∈ L(M), pois λ contém zero (valor par) ocorrências do símbolo a. Da mesma forma, qualquer 
sequência que só contenham b’s deverá ser reconhecida por M: p.ex. bbbb, que contém zero ocorrências de a’s. 
Tente construir um AFD reconhecedor para L(M), e confira a sua resposta no gabarito. Teste seu AFD com algumas 
das sequências acima, sempre observando se o processamento levou a um estado coerente. Em especial, teste com 
as sequências: λ, b, bb, bbb, bba, bbbb, a, ab, aba, abaa, e abab, baaa, abab, e babb, dentre outras. 
4.3 Exercícios resolvidos 
Para cada L(M) abaixo: i. Enumere algumas sequências que pertençam e que não pertençam a L(M); e ii. Construa 
um AFD para reconhecer L(M). 
g) I = { a, b }. L(M) = sequências em que o segundo símbolo é a. 
h) I = { a, b }. L(M) = sequências em que o penúltimo símbolo é a. 
 Teste com as sequências: λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, aaba, abaa, e aabba, dentre outras. 
i) I = { 0, 1 }. L(M) = sequências que contenham dois símbolos 1 consecutivos. 
 Teste com as sequências: λ, 0, 1, 00, 001, 010, 0101, 01010, 01011, 010110, dentre outras. 
j) I = { 0, 1 }. L(M) = { α ∈ I* | α possui sufixo 101 } 
 Teste com as sequências: λ, 0, 01, 10, 11, 101, 11101, 1011, 1011101, 10101, 101101, dentre outras. 
k) I = { a, b }. L(M) = { α ∈ I* | em α, toda ocorrência de símbolo a é imediatamente sucedida por um símbolo b } 
Observe que as sequências ab, abb, ababb, abbabbbab, deverão ser aceitas por M. Uma sequência a ser 
rejeitada deve ter um símbolo a que não seja imediatamente sucedido por b, como nas sequências: a, ba, 
aba, e ababba. Se identificarmos, em α, o símbolo a que “não respeita a regra”, α não será reconhecida. 
Importante notar que a sequência vazia deve ser aceita, pois λ NÃO CONTÉM nenhum símbolo a que não é 
imediatamente sucedido por b. Da mesma forma, deverão ser aceitas todas as sequências que não possuam 
nenhum símbolo a: b, bb, bbb, bbbb, … Nenhuma delas possui um a que “comprometa o reconhecimento”. 
l) I = { 0, 1 }. L(M) = sequências de comprimento par e finalizadas pelo símbolo a 
 Teste com as sequências: λ, a, b, aa, ab, ba, bb, aaa, aba, bbb, aaaa, aaab, aaba, abba, dentre outras. 
4.4 Gabarito dos exercícios resolvidos 
Possíveis respostas dos exemplos/exercícios: podem existir outros autômatos para uma mesma linguagem L(M). 
d) 
e0
b
e2
e1
a
be4
b
b
a e3 a
a
b
a
 
f) 
a
a
e0 e1b b
 
 
 
g) 
a
e2
e0 e1
a,b
a,b
e1
b
a,b
 
h) 
a
e2
e0 e1
a
a
b
e3
b b
a
b
 
 
i) 
1
e2e0 e1
1
0,1
0
0
 
j) 
0
e3e0 e1
1
0
e2
1
1
0
1
0 
 
k) 
e0 e1
a a
e2
a,b
b
b
 
l) 
a,b
e2e0 e1
a,b
b a