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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
1. As seguintes afirmac¸o˜es sa˜o verdadeiras ou falsas? Justifique (prove) suas respostas.
(a) Sejam dois AFDs M1 e M2. L(M1) = L(M2) se e somente se M1 = M2.
Resposta: Falsa. Uma mesma linguagem pode ser reconhecida por AFDs diferentes.
Por exemplo, todos os AFDs (Q,Σ, δ, q0, F ) com F = ∅ reconhecem a linguagem vazia.
Por outro lado, note que a afirmac¸a˜o: L(M1) = L(M2) se M1 = M2, (sem “somente
se”) e´ trivialmente verdadeira, por definic¸a˜o de linguagem de um autoˆmato.
(b) Se N = (Q,Σ, δ, q0, F ) e´ um AFN e F = Q enta˜o L(N) = Σ
∗.
Resposta: Falsa. Como contraexemplo, considere o AFNN = ({q0}, {0, 1}, δ, q0, {q0}),
com δ(q0, a) = ∅ para a ∈ {0, 1, ε}. Claramente, F = Q; no entanto, a linguagem re-
conhecida pelo autoˆmato e´ L(N) = {ε} 6= Σ∗.
(c) Se L ⊆ Σ∗ para um alfabeto Σ enta˜o L ∩ Σ e´ regular.
Resposta: Verdadeira. A linguagem Σ e´ finita e portanto sua intersec¸a˜o com L
tambe´m e´ finita. Toda linguagem finita e´ regular.
(d) Se o complemento de L e´ finito enta˜o L e´ regular.
Resposta: Verdadeira. Se L′ = L e´ uma linguagem finita, enta˜o e´ regular. A classe
das linguagens regulares e´ fechada sobre a complementac¸a˜o, portanto L′ = L tambe´m
e´ regular.
(e) A unia˜o de um nu´mero infinito de linguagens regulares e´ regular.
Resposta: Falsa. Como contraexemplo, considere a linguagem na˜o-regular L =
{0n1n|n ≥ 0}. Esta linguagem e´ a unia˜o de infinitas linguagens Li = {0i1i}, com
i = 0, 1, 2, . . . Cada Li e´ uma linguagem finita (conte´m uma u´nica cadeia) e, portanto,
regular.
2. (a) Enuncie o Lema do Bombeamento para linguagens regulares.
Resposta: Para toda linguagem regular L existe um nu´mero p, denominado compri-
mento de bombeamento, tal que, se w e´ qualquer cadeia de L de comprimento |w| ≥ p,
enta˜o w pode ser dividida na forma w = xyz, satisfazendo as condic¸o˜es: (1) xyiz ∈ L,
para i ≥ 0, (2) |y| > 0 e (3) |xy| ≤ p.
(b) Explique por que a segunda condic¸a˜o do Lema, |y| > 0, e´ necessa´ria.
Resposta: Sem essa condic¸a˜o, o Lema seria trivialmente verdadeiro para qualquer
linguagem L, inclusive as na˜o-regulares. Para qualquer cadeia w ∈ L, poderiamos
fazer, e.g., x = y = ε e z = w, e enta˜o xyiz = w ∈ L, para i ≥ 0.
(c) Prove que a linguagem L = {w#xwy|x, y, w ∈ {a, b}∗} na˜o e´ regular.
Resposta: Suponha L regular, e seja p seu comprimento de bombeamento. Considere
a cadeia s = ap#bapb. Claramente, s ∈ L, com w = ap, x = y = b. Tambe´m, |s| ≥ p.
Aplicamos o Lema do Bombeamento dividindo s em treˆs partes s = s1s2s3. A condic¸a˜o
(3) do Lema implica que s1s2 = a
k, com k ≤ p. A condic¸a˜o (2) implica que s2 = aj,
com 0 < j ≤ k. Bombeando para cima, obtemos s1s22s3 = ap+j#bapb. Verificamos
agora se esta cadeia tem a forma exigida na definic¸a˜o de L. A subcadeia w e´ aquela
que esta´ a` esquerda da ocorreˆncia de #, e enta˜o deve ser w = ap+j. No entanto, essa
subcadeia na˜o aparece a` direita de #. Concluimos que s1s
2
2s3 /∈ L, o que implica que L
na˜o satisfaz o Lema. Portanto, L deve ser na˜o-regular.
Atenc¸a˜o: note que bombear s para baixo produz uma cadeia que sim esta´ em L. Nesse
caso, s1s3 = a
p−j#bapb ∈ L, pois essa cadeia tem a forma w#xwy, com w = ap−j,
x = baj e y = b.
3. Sejam dois AFNs N1 = (Q1,Σ, δ1, q1, F1) e N2 = (Q2,Σ, δ2, q2, F2) que reconhecem as lingua-
gem L1 = L(N1) e L2 = L(N2), respectivamente. Vimos em aula que a classe das linguagens
regulares e´ fechada sobre a concatenac¸a˜o. Defina formalmente um AFN N = (Q,Σ, δ, q0, F )
que reconhec¸a a linguagem L1 ◦L2. Para definir a func¸a˜o de transic¸a˜o delta, utilize a forma
δ(q, a) =
{
δ1(q, a) se . . .
...
Resposta: Q = Q1 ∪Q2, q0 = q1, F = F2 e, para qualquer q ∈ Q e a ∈ Σε,
δ(q, a) =

δ1(q, a) se q ∈ Q1 e q /∈ F1
δ1(q, a) se q ∈ F1 e a 6= ε
δ1(q, a) ∪ {q2} se q ∈ F1 e a = ε
δ2(q, a) se q ∈ Q2
4. Seja um AFNs N = (Q,Σ, δ, q0, F ) com 10 estados (|Q| = 10), alfabeto de 5 s´ımbolos
(|Σ| = 5) e 3 estados de aceitac¸a˜o (|F | = 3).
(a) Qua´ntos elementos possui o domı´nio da func¸a˜o δ? Justifique sua resposta.
Resposta: O domı´nio de δ e´ Q × Σε, cuja quantidade de elementos e´ |Q| × |Σε| =
10× (5 + 1) = 60.
(b) Se converte o AFN em um AFD equivalente usando o procedimento visto em aula (e
explicado no livro-texto), qual sera´ a quantidade de estados desse AFD? Justifique sua
resposta.
Resposta: A conversa˜o produz um AFD cujo conjunto de estados e´ P(Q). Assim, a
quantidade de estados do AFD e´ |P(Q)| = 2|Q| = 210 = 1024.