Tema 03 - AFDs Reconhecedores de Linguagens - TEXTO DE APOIO

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
TEMA 3: AFD’s para Reconhecimento de Linguagens 
 
TEXTO PARA APOIO AO ESTUDO 
3.1 Autômatos Finitos como Reconhecedores de Linguagens 
Neste tema vamos examinar a construção de autômatos finitos cuja finalidade é o reconhecimento de sequências 
que pertençam a linguagens específicas. Como veremos a seguir, os “autômatos reconhecedores” não geram 
sequências de saída: eles apenas “indicam” se uma dada sequência de entrada é aceita como pertencendo a uma 
linguagem. Vamos examinar um exemplo abaixo para sermos mais específicos. 
3.2 Um exemplo de AFD reconhecedor 
Como primeiro exemplo, vamos examinar melhor o AFD M1 abaixo. 
e0
1
e3
0
e4
e1
0
1e2
1
0
1
0
0
1
 
Exemplo 2.1: um AFD reconhecedor M1 
Examinemos como funciona um AFD reconhecedor: 
 Os estados não geram nenhuma saída: não existe símbolo de saída indicado no rótulo de cada estado. 
Assim, um AFD de reconhecimento não possui alfabeto de saída O. 
 Alguns estados são representados por um círculo com “linha dupla”. No caso de M1, temos e2 e e4. 
Tais estados são chamados ESTADOS FINAIS ou TERMINAIS (podemos dizer estados de reconhecimento). 
 Se um AFD M, ao processar uma sequência de entrada α, terminar em um estado final, dizemos que: 
M reconhece (ou aceita) a sequência α. 
De forma equivalente, dizemos que α é aceita ou reconhecida por M. 
 Se um AFD M, ao processar uma sequência de entrada α, terminar em um estado não final, dizemos que: 
M rejeita (ou não reconhece ou não aceita a sequência α). 
De forma equivalente, dizemos que α é rejeitada ou α não é aceita (ou não reconhecida) por M. 
Como exercício, tente simular o processamento de várias sequências de entrada no autômato M1. Verifique em 
quais deles M1 termina em um estado final ou não-final. Depois compare suas respostas com as informações 
abaixo. MAS LEMBRE-SE: comece o processamento de cada sequência a partir do estado inicial e0. 
 Para sequências de entrada em que M1 termina seu processamento em e2 ou e4; temos que: 
M1 aceita (ou reconhece) as sequências: 01, 10, 001, 011, 100, 110, … 
 Para sequências de entrada em que M1 termina seu processamento em e0, e1 ou e3; temos que: 
M1 rejeita (ou não aceita ou não reconhece) as sequências: λ, 0, 1, 00, 11, 000, 010, 101, 111, … 
 Como continuação do exercício, enumere todas as sequências de comprimento 4; verifique quais são e 
quais não são reconhecidas por M1. 
3.3 Definição: AFD (Autômato Finito Determinístico) para reconhecimento 
Um autômato finito determinístico (AFD) reconhecedor M é uma quíntupla: M = (Σ, E, δ, e0, F), onde: 
• Σ – Alfabeto (de símbolos) de entrada; 
• E – Conjunto finito de estados; 
• δ – Função de transição δ: E x Σ → E. Estando no estado e e lendo a entrada i, M vai para o estado δ(e,i); 
• e0 – Estado inicial; 
• F – Conjunto não vazio de estados finais: F ⊂ E. 
Desta forma, M pode ler e processar qualquer sequência de entrada α ∈ Σ*. Dizemos que: 
• α é aceita (ou reconhecida) por M se, iniciando em estado e0 e processando todos os símbolos de α, 
M terminar o processamento em um estado final ef ∈ F. 
• Caso contrário; isto é, se M terminar o processamento em um estado en ∉ F; dizemos que 
M rejeita (ou não aceita, ou não reconhece) α. 
3.4 Identificando a linguagem aceita por um AFD reconhecedor 
Agora surge outra questão: identificar TODAS as sequências (e apenas estas) reconhecidas por um AFD. 
Já sabemos que um AFD M pode ler qualquer palavra α ∈ Σ*, reconhecendo algumas e rejeitando outras. Desta 
forma, M particiona o conjunto Σ* em dois subconjuntos disjuntos: 
Σ* = L ∪ L’ onde L é a linguagem (conjunto de sequências) contendo TODAS as sequências aceitas por M; e 
L’ é a linguagem contendo TODAS as sequências rejeitadas por M. 
Formalmente, se M é um AFD reconhecedor, definimos L(M) como a LINGUAGEM ACEITA (ou RECONHECIDA) por 
um AFD M da seguinte forma: 
L(M) = { α ∈ Σ* | α é aceita por M } 
Um desafio é caracterizar corretamente, em português, a linguagem reconhecida por um autômato reconhecedor. 
Vejamos alguns exemplos, primeiro definindo L(M) por enumeração, e depois usando a linguagem corrente. 
3.5 Exercícios comentados 
Caracterizar, em português, linguagens reconhecidas por AFD’s. Extraído do livro-texto, pág. 448 (Fig. 8.6). 
 
 
Comentário: apenas a sequência é aceita pelo AFD. Por enumeração: L = { 0 } 
Resposta correta: Apenas a sequência 0 é reconhecida. 
 
Comentário: apenas duas sequências são aceitas pelo AFD. Por enumeração: L = { 0, 1 } 
Respostas corretas: - Apenas as sequências 0 e 1; ou 
- Todas as sequência de comprimento UM. 
 
Comentário: infinitas sequências são reconhecidas. Por enumeração: L = { λ, 11, 1111, 111111, … } 
Respostas corretas: - Sequência vazia, e todas as sequências contendo apenas ocorrências do símbolo 1 e 
 com quantidade par de símbolos. 
- Todas as sequências de comprimento PAR formadas apenas pelo símbolo 1. 
- Todas as sequências de comprimento PAR que não tenham ocorrências do símbolo 0. 
 
Comentário: infinitas sequências são reconhecidas. Por enumeração: L = { 10, 010, 0010, 00010, … } 
Respostas INCORRETAS: - Todas as sequências de sufixo 0. 
- Todas as sequências de sufixo 10. 
- Todas as sequências terminadas por de sufixo 10, antecedido por símbolos 0. 
- Todas as sequências que contenham apenas um símbolo 0. 
Observe que todas as descrições acima estão erradas. Devemos especificar que toda sequência 
reconhecida deve ter o sufixo 10, mas também que as demais ocorrências de símbolos (se existirem) 
só podem ser do símbolo 0. 
Respostas corretas: - Sequências de sufixo 10 que contenham uma única ocorrência do símbolo 1. 
- Sequências contendo apenas um símbolo 1, sendo este necessariamente o penúltimo 
 símbolo da sequência. 
3.6 Exemplos 
Para cada AFD reconhecedor M abaixo, vamos examinar como descrevemos, em português, a linguagem L(M). 
Vamos assumir que o alfabeto de entrada já está implícito, como no item c). 
Atenção: ao descrevermos as linguagens, as especificações devem ser “precisas”. Ou seja; i. não podemos “incluir” 
sequências que não são aceitas, e ii. não podemos deixar de contemplar todas as sequências que são reconhecidas. 
a) 
a,b
e0
a,b
e1
 
b) 
b a,b
a
e0 e1
 
c) 
a,b
e1
a,b
e0
 
d) 
a
e0a,b
b
e1
 
e) 
b
e2e0 e1
b a,b
a
a 
f) 
b
e2e0 e1
b a,b
aa
 
g) 
e0
1
e3
0
e4
e1
0
1e2
1
0
1
0
0
1
 
 
 
 
 
 
 
 
 
3.7 Gabarito 
a) Apenas a sequência vazia. Ou seja, L(M) = { λ }. 
b) Sequências formadas (apenas) pelo símbolo a. Ou 
Sequência vazia e sequências que só tenham ocorrências do símbolo a. Ou 
Sequências que não tenha nenhuma ocorrência do símbolo b. 
c) Sequências contendo uma quantidade ímpar de símbolos. Ou 
Toda sequência de comprimento ímpar. 
d) Linguagem vazia (conjunto vazio). Ou seja, L(M) = { }. 
Observe que o AFD não reconhece nenhuma sequência. 
OBS.: compare este autômato com o da letra a). 
e) Sequências que contenham dois símbolos b’s consecutivos. Ou 
Sequências que contenham duas ocorrências consecutivas do símbolo b. Ou 
Toda sequência que contenha a subsequência bb. 
f) Sequências que contenham dois símbolos b’s. Ou 
Sequências que contenham duas ocorrências do símbolo b. Ou 
Toda sequência que contenha dois ou mais símbolos b. 
g) Toda sequência ou iniciada por 0 e finalizada por 1, ou iniciada por 1 e finalizada por 0. Ou 
Sequências em que o símbolo inicial e o último símbolo sejam distintos. 
 
 
 
 
 
 
ALGUMAS DEFINIÇÕES, EXEMPLOS E EXERCÍCIOS CONTIDOS NESTE MATERIAL DE APOIO AO ESTUDO FORAM 
EXTRAÍDOS DA SEGUINTE PUBLICAÇÃO: 
GERSTING, J. L. 
FUNDAMENTOS MATEMÁTICOS PARA A CIÊNCIA DA COMPUTAÇÃO. 5ª ed., Rio de Janeiro: LTC, 2004.