Notas de Aula Teoria da Computação III e IV

Prévia do material em texto

TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 15 
 
 
III AFD DE RECONHECIMENTO 
Além dos AFD’s de processamento, vistos na anterior, autômatos finitos também podem ser 
definidos para atuarem como “reconhecedores”. 
A definição de um AFD de reconhecimento não contém um alfabeto de saída, sendo 
especificado apenas o alfabeto de entrada I. Ao ler qualquer sequência α ∈ I*, o AFD reconhecedor 
irá reconhecer (ou aceitar) apenas algumas destas sequências, e não reconhecer (não aceitar ou 
rejeitar) outras. 
AFD
RECONHECEDOR
*
ACEITA
REJEITA
 
III.1 AFD´S RECONHECEDORES 
Um Autômato Finito Determinístico reconhecedor M terá as seguintes características: 
• Seus estados NÃO GERAM SAÍDA: apenas o alfabeto de entrada I é definido. 
• Seu conjunto de estados E é pode ser particionado em dois conjuntos E = EF ∪∪∪∪ EF’, onde: 
EF : conjunto de ESTADOS FINAIS 
EF’: conjunto de ESTADOS NÃO–FINAIS 
• NOTAÇÃO GRÁFICA: 
 
efinal enão-final
 
 ESTADO FINAL ESTADO NÃO-FINAL 
• No processamento de uma sequência entrada α ∈∈∈∈ I*, M pode terminar em um estado: 
FINAL ⇒ M RECONHECE ou ACEITA α 
NÃO-FINAL ⇒ M NÃO RECONHECE, NÃO ACEITA, ou REJEITA α 
Exemplo: o AFD a seguir tem cinco estados sendo que e2 e e4 são estados finais. 
e0
1
e3
0
e4
e1
0
1e2
1
0
1
0
0
1
 
Processamento do AFD á esquerda: 
M ACEITA as sequências: 01, 011, 110, … 
M REJEITA as sequências: 0, 00, 101, … 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 16 
 
 
III.2 LINGUAGENS RECONHECIDAS POR UM AFD 
Como já visto, um AFD M pode ler qualquer palavra α ∈ I*, reconhecendo algumas e 
rejeitando outras. Desta forma, M particiona o conjunto I* em dois subconjuntos: 
I* = S ∪∪∪∪ S’ onde S = linguagem reconhecida por M; 
S’ = conjunto das sequências rejeitadas por M. 
Dizemos então que M reconhece a linguagem S. 
 
Formalmente, definimos a Linguagem reconhecida por M, notada por L(M), como: 
L(M) = { αααα ∈∈∈∈ I* | M reconhece αααα } 
Exercício: caracterize, EM PORTUGUÊS, as linguagens reconhecidas pelos AFD’s abaixo. 
Apostila I, PROBLEMA PRÁTICO 40, pág. 448 (Fig. 8.6), A SER RESOLVIDO EM AULA: 
 
 
PADRÃO DE RESPOSTAS: 
a. L(M) = { 0 } Resp.: Apenas a sequência 0 
b. L(M) = { 10, 010, 0010, 00010, … } Resp.: Sequências de sufixo 01 que contenham um 
único símbolo 1 
c. L(M) = { 0, 1 } Resp.: Apenas as sequências 0 e 1 
d. L(M) = { λ, 11, 1111, 111111, … } Resp.: Sequências de comprimento par que não 
contenham o símbolo 0 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 17 
 
 
EXERCÍCIOS RESOLVIDOS EM AULA: Caracterize L(M), em português, para cada AFD abaixo. 
(a) 
a,b
e0
a,b
e1
 
L(M): 
Apenas a sequência vazia, ou apenas λ. 
 
 
(b) 
b a,b
a
e0 e1
 
L(M): 
Sequências que não contenham o símbolo 1. 
 
(c) 
b
e2e0 e1
b a,b
a
a
 
L(M): 
Sequências que contenham dois símbolos b’s 
consecutivos. 
 
(d) 
e3
0
1
0
1
0,1
e1
e0
e2
0
1
 
L(M): 
Sequências que não contenham nenhum símbolo 
sucedido por outro igual. 
 
(e) 
a,b
e1
a,b
e0
 
L(M): 
Sequências de comprimento par. 
 
 
(f) 
a
e0
a,b
b
e1
 
L(M): 
Conjunto vazio 
(M não reconhece nenhuma sequência) 
 
 
(g) 
b
e2e0 e1
b a,b
aa
 
L(M): 
Sequências que contenham dois símbolos b. 
 
 
(h) 
e0
1
e3
0
e4
e1
0
1e2
1
0
1
0
0
1
 
L(M): 
Sequências em que o símbolo inicial seja 
diferente do último símbolo. 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 18 
 
 
III.3 CONSTRUINDO UM AFD DE RECONHECIMENTO 
Dada uma descrição da linguagem L(M), construiremos o AFD correspondente. Consideraremos 
implicitamente o alfabeto de entrada I = { a, b }, ou então, quando for o caso, o alfabeto I = { 0, 1 }. 
EXEMPLOS RESOLVIDOS EM AULA: 
Para cada exemplo, vamos enumerar algumas das sequências que obedecem ou não à descrição 
dada. Desta forma, devemos construir um autômato que, ao ler qualquer sequência a ser reconhecida, 
termine seu processamento em um estado final; e o processamento de qualquer sequência que não deve 
ser reconhecida leva o autômato a um estado não-final. 
EXEMPLOS RESOLVIDOS EM SALA – Construir AFD’s que reconheçam as seguintes linguagens:
a. Sequências iniciadas com o símbolo ‘a’. 
 
α ∈ L(M): a, aa, ab, aaa, aab, aba, abb, aaaa, … 
α ∉ L(M): λ, b, ba, bb, baa, bab, bba, bbb, … 
 
 
 
b. Seqs finalizadas pelo símbolo ‘a’. 
 
α ∈ L(M): a, aa, ba, aaa, aba, baa, bba, aaaa, … 
α ∉ L(M): λ, b, ab, bb, aab, abb, bab, bbb, … 
 
 
 
 
 
c. Seqs iniciadas por dois símbolos iguais. 
 
α ∈ L(M): 
α ∉ L(M): 
 
 
 
d. Seqs terminadas com dois símbolos iguais. 
 
α ∈ L(M): 
α ∉ L(M): 
 
 
 
 
e. Seqs com a’s e b’s de comprimento par. 
 
α ∈ L(M): λ, aa, ab, ba, bb, aaaa, aaab, … 
α ∉ L(M): a, b, aaa, aab, aba, abb, baa, bab, … 
 
 
 
f. Seqs contendo um nº par de ‘a’s. 
 
α ∈ L(M): λ, b, aa, bb, aab, aba, bbb, … 
α ∉ L(M): a, ab, ba, abb, bab, bba, aaa, … 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 19 
 
 
g. Seqs em que o 2º símbolo é ‘a’. 
 
α ∈ L(M): 
α ∉ L(M): 
a
e2
e0 e1
a,b
a,b
e1
b
a,b
 
 
h. Seqs em que o penúltimo símbolo é ‘a’. 
 
α ∈ L(M): 
α ∉ L(M): 
a
e2
e0 e1
a
a
b
e3
b b
a
b
 
 
i. Seqs que contenham dois ‘1’s consecutivos. 
 
α ∈ L(M): 
 
α ∉ L(M): 
 
1
e2e0 e1
1
0,1
0
0
 
 
j. Seqs terminadas com ‘101’. 
 
α ∈ L(M): 
 
α ∉ L(M): 
 
0
e3e0 e1
1
0
e2
1
1
0
1
0
 
 
k. Seqs em que todo ‘a’ é sucedido por ‘b’. 
 
α ∈ L(M): λ, b, ab, bb, abb, bab, bbb, bbbb, … 
 
α ∉ L(M): a, aa, ba, bba, aba, baa, aab, aaa, … 
 
e0
e1
a
a
e3 a,b
b
b
 
 
l. Seqs de comprimento par finalizadas por ‘a’. 
 
α ∈ L(M): 
 
α ∉ L(M): 
 
a,b e2
e0 e1
a,b
b
a
a,b e3
 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 20 
 
 
III.4 EXERCÍCIOS 
APOSTILA: pág. 463 em diante: 
• para os exercícios 19) (menos item b), 20), e 32) construir AFD reconhecedores das 
linguagens descritas em cada item; 
• caracterizar as linguagens reconhecidas pelos ADF’s dos exercícios do 25) ao 30); 
 
9) Descreva, em português, a linguagem L(M) para cada AFD M, a seguir. 
a) 
e0 e1
0,1
0,1
 
 
 
d) 
0,1
e1
1,0
e0
 
 
 
g) 
0
1,0
e2
1
e0
0
1
e1
 
 
b) 
a
b b
e1
a
e0
 
 
 
e) 
e0 e1
1,0
1
0
 
 
h) 
0
1,0
e1
e2
1
e0
0
1
 
 
c) 
1
e1
1,0
e0
0
 
 
 
f) 
e0 e11,0
0,1
 
 
 
i) 
0
1,0
e2
1e1
0
1
e0
 
 
j) 
1
0,1
e2
0
e0
e1
0,1
 
 
 
 
k) 
1
0,1
0
e1
e0
e2
0,1
 
 
 
l) 
e0
0
1
1
0
1
e1 e2
0
1
e4e3
0
0
1
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 21 
 
 
m) 
0
1,0
e2
1
e0
0
1
e1
 
 
 
 
n) 
0
1
1
0
e1
e2
e3e0
1
0
0,
1
 
 
o) 
1
1
e0
0,1
e1
00
e2
 
 
 
10) Para o AFD M, representado a seguir: 
a) Dê 5 exemplos de palavras reconhecidas por M. 
b) Descreva L(M) em português 
c) Em que implicaria o fato de e0 não ser um estado final?e4
0
e1
e0
e3
1
1
e2
0
0
1
0
1
1
0
 
11) Para o AFD M, representado a seguir: 
a) Dê 5 exemplos de palavras reconhecidas por M. 
b) Descreva L(M) em português 
c) O que implicaria o fato de e0 também ser um estado final? e0
e1
e2
e5
e3
e4
0
1
0
0
1
1
1
1
0
0
0,1
 
12) Para o AFD M, representado a seguir: 
a) Dê 5 exemplos de palavras reconhecidas por M. 
b) Descreva L(M) em português 
c) O que implicaria o fato de e0 não ser um estado final? e3
0 1
0
1
0,1
e1
e0
e2
0
1
 
13) Para I = { a, b }, construir os grafos de AFD’s que reconheçam as seguintes linguagens: 
a) Palavras de comprimento par. 
b) Palavras de comprimento par E terminadas com a. 
c) Palavras de comprimento ímpar E terminadas com a. 
d) Palavras que possuam mais de um a E mais de um b. 
e) Palavras que possuam mais de um a OU mais de um b. 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 22 
 
 
f) Palavras em que TODO b é precedido de a. 
g) Palavras em que TODO b é sucedido por a. 
h) Palavras em que o símbolo inicial seja igual ao símbolo final. 
i) Palavras em que o símbolo inicial seja diferente do símbolo final. 
j) Palavras que possuam dois símbolos a’s consecutivos. 
k) Palavras que NÃO possuam dois símbolos a’s consecutivos. 
l) Palavras que NÃO possuam repetição consecutiva de um mesmo símbolo. 
m) Palavras que NÃO terminem com dois a’s consecutivos. 
n) Palavras com 3 ou mais símbolos, sendo que ambos – a e b – deverão estão presentes. 
o) Palavras que NÃO tenham a’s isolados. Ou seja, TODO símbolo a tem um vizinho igual a ele. 
14) Para o alfabeto I = { 0, 1 }, construir AFD’s que reconheçam as seguintes linguagens: 
a) Palavras com quantidade par de 0’s. 
b) Palavras em que o penúltimo dígito seja 0. 
c) Palavras em que o 2º símbolo seja igual ao 4º símbolo. 
d) Palavras que tenham o sufixo ‘101’. 
e) Palavras que tenham o sufixo por ‘110’. 
f) Palavras terminadas por dois símbolos diferentes. 
g) Palavras em que a “soma dos seus bits” não seja maior do que 3. 
h) Palavras que não possuam três 1’s consecutivos. 
15) Para o alfabeto de entrada I = { a, b, c, d, e }, construir um AFD’s que reconheçam as linguagens: 
a) Palavras iniciadas por vogal. 
b) Palavras que NÃO comecem com consoante. 
c) Qual a diferença dos conjuntos definidos nos itens a) e b)? 
16) Construir um AFD que reconheça a linguagem formadas pelas palavras do alfabeto I = { a, b } que 
contenham um n° par de a’s E um n° par de b’s (não necessariamente o mesmo n° de a’s e b’s). 
III.5 RESPOSTAS DE ALGUNS EXERCÍCIOS: 
9) Assumindo o alfabeto de entrada { 0, 1 } ou { a, b }, dependendo de cada MEF, temos: 
a) Seqs de comprimento ímpar. 
b) Seqs: vazia e sequências terminadas com ‘b’. OU TAMBÉM : Seqs que não terminem com ‘a’. 
c) Seqs que não contenham o símbolo ‘1’. 
d) Apenas a sequência vazia. 
e) Conjunto vazio ou seja: nenhuma sequência é reconhecida. 
f) Conjunto vazio ou seja: nenhuma sequência é reconhecida. 
g) Seqs que contenham o (ao menos um) símbolo ‘1’. 
h) Seqs não vazias contendo apenas símbolos ‘0’ (um ou vários). 
i) Apenas a sequência vazia. 
j) Seqs iniciadas com o símbolo ‘1’. 
k) Seqs que não iniciem com o símbolo 1. 
l) Seqs em que os dois últimos símbolos são diferentes. 
m) Qualquer seq não vazia. 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 23 
 
 
n) Seqs que contenham ambos os símbolos ‘0’ e ‘1’. 
o) Seqs que não contenham dois ‘1’s consecutivos. 
12) 
a) λ, 0, 1, 01, 10, 010, 101, 0101, 1010, … 
b) Seqs que não tenham repetição consecutiva de nenhum símbolo 
c) O conjunto de sequências reconhecido não incluiria a seq vazia. 
13) 
b) 
a
b
s2
s2
a,b
a,bs0 s1
a,b
 
c) 
a
b
s1
s2
a,b
a,b
s0
 
f) 
a
b
a
s1
s2
s0
b
a,b
 
n) 
s0
b
s3
b
s6
b
s1
s4
s2
a
a
a
s5
b
a
b
a
a,b
a,b
 
i) 
sa
b
s3
a
s4
sb
a
bs2
b
a
b
a
a
b
 
 
 
14) b) 
s0
s3
s1
0
s2
0
1
0
1
1
1
0