1ª Prova de Autômatos e Computabilidade - 1º/2013 - Lucero - UnB

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
1. Queremos utilizar um autoˆmato finito (AFD ou AFN) para determinar se um texto conte´m
alguma ocorreˆncia das palavras web ou ebay. O autoˆmato recebe o texto completo como
cadeia de entrada, e aceita se esse texto conte´m alguma das palavras (subcadeias) procura-
das. Considere como alfabeto Σ ao conjunto de todas as letras minu´sculas e maiu´sculas do
alfabeto ingleˆs, os s´ımbolos de pontuac¸a˜o e o espac¸o em branco. Por exemplo, o autoˆmato
aceita a cadeia
w = The company provides web access to the software previously distributed,
pois w conte´m a subcadeia web.
Desenhe o diagrama de estados do autoˆmato.
Resposta:
q0
q1 q2 q3
q4 q5 q6 q7
Σ
w
e b
e
b a y
Σ
Σ
Nota: o ro´tulo Σ sobre transic¸o˜es representa todos os s´ımbolos do alfabeto.
2. Defina, formalmente, o que significa dizer que um AFN N = (Q,Σ, δ, q0, F ) aceita uma
cadeia w.
Resposta: N aceita uma cadeia w = w1w2 . . . wk, com wi ∈ Σ∪{ε} para i = 1, 2, . . . , k,
se existe uma sequeˆncia de estados r0, r1, . . . ,rk, com ri ∈ Q para i = 0, 1, . . . , k, tal que
(1) r0 = q0, (2) ri+1 ∈ δ(ri, wi+1), para i = 0, 1, . . . , k − 1, e (3) rk ∈ F .
3. Prove que toda linguagem descrita por uma expressa˜o regular e´ uma linguagem regular.
Dica: utilize a definic¸a˜o de expressa˜o regular.
Resposta: Por definic¸a˜o, uma expressa˜o regular R sobre um alfabeto Σ e´ alguma das
seguintes seis alternativas: (1) a, onde a ∈ Σ, (2) ε, (3) ∅, (4) R1 ∪R2, onde R1 e R2 sa˜o
expresso˜es regulares, (5) R1 ◦R2, onde R1 e R2 sa˜o expresso˜es regulares, ou (6) R∗1, onde
R1 e´ uma expressa˜o regular. Essas expresso˜es representam as linguagens {a}, {ε}, { },
L(R1) ∪ L(R2), L(R1) ◦ L(R2) e L(R1)∗, respectivamente, onde L(R) denota a liguagem
descrita por R. As linguagens dos casos (1), (2) e (3) sa˜o regulares, pois sa˜o reconhecidas,
respectivamente, pelos seguintes AFNs:
a
Para os casos (4), (5) e (6), usamos o fato de que a classe das linguagens regulares e´
fechada sobre as operac¸o˜es de unia˜o, concatenac¸a˜o e estrela. Portanto, se L(R1) e L(R2),
em (4) e (5), ou somente L(R1), em (6), sa˜o regulares, enta˜o sua unia˜o, concatenac¸a˜o e
operac¸a˜o estrela tambe´m sa˜o.
4. Seja A uma linguagem finita, e n o comprimento ma´ximo das cadeias de A (i.e., |w| ≤ n
para todo w ∈ A). Prove que todo AFD que reconhec¸e A tem pelo menos n + 1 estados.
Dica: lembre de como foi escolhido o comprimento de bombeamento na prova do Lema do
Bombeamento.
Resposta: Conforme visto na demostrac¸a˜o do Lema do Bombeamento, se um AFD tem
p estados, enta˜o p e´ um comprimento de bombeamento para a linguagem do autoˆmato
e as cadeias da linguagem que possuem comprimento maior ou igual a p podem ser
bombeadas. Se bombeamos uma cadeia “para cima”, obtemos outras infinitas cadeias da
linguagem, de comprimento maior que a cadeia original. Suponha, assim, que um AFD
que reconhece A tem uma quantidade de estados p ≤ n. Enta˜o, existe pelos menos uma
cadeia w ∈ A, de comprimento maior ou igual a p, que pode ser bombeada. Bombeando
“para cima” essa cadeia obtemos infinitas outras cadeias de A de comprimento maior
que n. No entanto, isso contradiz a afirmac¸a˜o inicial de que A e´ finita e de que n e´ o
comprimento ma´ximo de suas cadeias. Portanto, nenhum AFD que reconhec¸a A pode ter
uma quantidade de estados p ≤ n.
5. Prove que a linguagem L = {0n1m| 0 ≤ n ≤ m} na˜o e´ regular.
Resposta: Suponha que L e´ regular, e seja p o comprimento de bombeamento. Esco-
lhemos a cadeia de teste s = 0p1p, que pertence a L e tem comprimento maior que p.
Subdividimos a cadeia na forma s = xyz. Pela condic¸a˜o (3) do Lema do Bombeamento,
xy deve conter unicamente 0s, e pela condic¸a˜o (2), y conte´m pelo menos um 0. Supo-
nha, enta˜o, y = 0k, com 1 ≤ k ≤ p. Pelo Lema do Bombeamento, a cadeia xyyz deve
pertencer a L. No entanto, xyyz = 0p+k1p e a quantidade de 0s e´ maior que a de 1s, o
que contradiz o Lema. Assim, L na˜o pode ser regular.
6. Considere o seguinte AFN, com alfabeto Σ = {0, 1}.
q0 q1 q2 q3
1
0,1
0,1 0,1
(a) Descreva a linguagem reconhecida pelo AFN.
Resposta: o AFN reconhece a linguagem composta por todas as cadeias que conteˆm
um 1 na penu´ltima ou na antepenu´ltima posic¸a˜o.
(b) Escreva uma expressa˜o regular equivalente ao AFN.
Resposta: R = (0 ∪ 1)∗1(0 ∪ 1)(ε ∪ 0 ∪ 1).