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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
1. Fornec¸a a definic¸a˜o formal de computac¸a˜o para um AFD M = (Q,Σ, δ, q0, F ) (i.e., defina
formalmente o que significa dizer que M aceita uma cadeia w ∈ Σ∗).
Resposta: M 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, wi+1) = ri+1, para i = 0, 1, . . . , k − 1, e (3) rk ∈ F .
2. Verdadeiro ou falso? Justifique sua resposta.
(a) (1 ponto) Todo subconjunto de uma linguagem regular e´ regular.
Resposta: Falso. Como contraexemplo, considere {0n1n|n ≥ 0} ⊆ {0, 1}∗. A pri-
meira linguagem na˜o e´ regular, e a segunda sim.
(b) Se a linguagem L e´ regular, enta˜o a linguagem L′ = {xy| x ∈ L e y /∈ L} tambe´m e´
regular.
Resposta: Verdadeiro. Note que L′ = L ◦ L, e que a classe das linguagens regulares
e´ fechada sobre a concatenac¸a˜o e a complementac¸a˜o.
(c) b∗a∗ ∩ a∗b∗ = a∗ ∪ b∗
Resposta: Verdadeiro. Note que ambn = bpaq, onde m,n, p, q sa˜o inteiros positivos,
se e somente se m = q e n = p = 0, ou m = q = 0 e n = p.
(d) L ◦ LR = {wwR|w ∈ L}, onde L e´ uma linguagem qualquer.
Resposta: Falso. Como contraexemplo, considere L = {ab, aab}. Then, L ◦ LR =
{abba, abbaa, aabba, aabbaa} e {wwR|w ∈ L} = {abba, aabbaa}.
3. Seja o AFN N = (Q,Σ, δ, q0, F ) que reconhece a linguagem L = L(N). Defina formalmente
um AFN N ′ = (Q′,Σ, δ′, q′0, F
′) que reconhec¸a a linguagem L∗.
Para definir a func¸a˜o de transic¸a˜o delta, utilize a forma
δ′(q, a) =
{
δ(q, a) se . . .
...
Resposta: Q′ = Q∪{q′0}, q
′
0 e´ um novo estado, F
′ = F ∪{q′0} e, para todo q ∈ Q
′ e a ∈ Σε,
δ′(q, a) =


δ(q, a) se q ∈ Q e q /∈ F
δ(q, a) se q ∈ F e a 6= ε
δ(q, a) ∪ {q0} se q ∈ F e a = ε
{q0} se q = q
′
0 e a = ε
∅ se q = q′0 e a 6= ε
4. (a) Prove que a linguagem L1 = {a
mbnar|m,n, r ≥ 0 e r ≥ m} na˜o e´ regular. Utilize o
Lema do bombeamento.
Resposta: Suponha L1 regular, e seja p seu comprimento de bombeamento. Considere
a cadeia w = apbpap. Claramente, s ∈ L1 e |s| = 3p ≥ p. Aplicamos o Lema do
Bombeamento dividindo w em treˆs partes w = xyz. A condic¸a˜o (3) do Lema implica
que xy = ak, com k ≤ p. A condic¸a˜o (2) implica que y = aj , com 0 < j ≤ k.
Bombeando para cima, obtemos xyyz = ap+jbpap. Nesta cadeia, m = p + j e r = p,
enta˜o m > r e, portanto, xyyz /∈ L1. Concluimos que L1 na˜o satisfaz o Lema e enta˜o
deve ser na˜o-regular.
(b) Prove que a linguagem L2 = {xyzy| x, y, z ∈ {0, 1}
+} e´ regular. Dica: encontre uma
expressa˜o regular que descreva a mesma linguagem.
Resposta: Note que, para qualquer cadeia w ∈ L2, se w termina com 0 enta˜o y termina
com 0. Como y esta´ repetido, enta˜o w tera´ uma outra ocorreˆncia de 0 dentro dela. O
mesmo acontece para qualquer cadeia em L2 que termine com 1, essa cadeia tera´ um
outra ocorreˆncia de 1 dentro dela. Assim, qualquer cadeia em L2 pertence a` linguagem
descrita pela expressa˜o regular R = (Σ+0Σ+0)∪(Σ+1Σ+1), onde Σ = {0, 1}. Tambe´m,
qualquer cadeia em L(R) pertence a L2: fazemos y igual ao s´ımbolo repetido (0 ou 1,
conforme o caso) e x, z iguais a`s subcadeias correspondentes a`s duas cocorreˆncias de
Σ+, respectivamente. Enta˜o, L2 = L(R) e e´ regular.
(c) Considere a linguagem regular L3 = L(R), onde R = 000(11)
∗1. Qual e´ o valor mı´nimo
de seu comprimento de bombeamento? Justifique sua resposta.
Resposta: Toda cadeia de L3 conte´m treˆs 0s seguidos de uma quantidade ı´mpar de 1s.
A menor cadeia e´ 0001, que na˜o pode ser bombeada para baixo (na˜o podemos diminuir
a quantidade de s´ımbolos). Qualquer outra cadeia pode ser bombeada, fazendo x =
000, y igual a` primeira ocorreˆncia da subcadeia 11, e z igual ao resto da cadeia. O
comprimento mı´nimo de bombeamento e´, portanto, p = 5.
5. Segundo o livro Klingon for the Galactic Traveler, na lingua klingon existem duas palavras
que significam “guerra”: veS e noH. A primeira se refere a` ideia abstracta da guerra, en-
quanto que a segunda se refere a uma guerra em particular. Suponha que, como medida de
prevenc¸a˜o e seguranc¸a, queremos monitorar mensagens internas do Impe´rio Klingon para
detectar refereˆncias a` guerra. O texto completo de uma mensagem pode ser considerado
como uma cadeia sobre um alfabeto Σ, e cada palavra desse texto como uma subcadeia.
Suponha que Σ conte´m todas as letras do alfabeto portugueˆs, em minu´scula e em maiu´scula,
os d´ıgitos de 0 a 9, os s´ımbolos de pontuac¸a˜o e o espac¸o em branco (indicado pelo s´ımbolo
⊔). Construa, enta˜o, um autoˆmato finito que aceite um texto em klingon se e´ste conte´m
alguma ocorreˆncia das palavras veS ou noH. Por exemplo, o autoˆmato deve aceitar a cadeia
w = tagh ⊔ noH ⊔ tugh (“A guerra comec¸ara´ logo”), pois conte´m a subcadeia noH.
Resposta:
q0
q1 q2 q3 q4
q5 q6 q7 q8
Σ
ε
v e S
ε
n o H
Σ
Σ
O ro´tulo Σ sobre transic¸o˜es indica qualquer s´ımbolo do alfabeto.