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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
Prof. Jorge C. Lucero
28 de setembro de 2015
Nome: Matr´ıcula:
1. (a) (1,5 pontos) Fazendo uma prova por construc¸a˜o, demonstre que todo AFN possui um
AFD equivalente.
Resposta: Seja o AFN N = (Q,Σ, δ, q0, F ). Construimos um AFD equivalente M =
(Q′,Σ, δ′, q′0, F
′) definindo, para R ⊆ Q, E(R) = {q ∈ Q| q pode ser atingido a partir
de R viajando-se o longo de 0 ou mais setas εem N}, e fazendo :
i. Q′ = P(Q),
ii. δ′(R, a) = {q ∈ Q| q ∈ E(δ(r, a)) para algum r ∈ R} =
⋃
r∈RE(δ(r, a)), para todo
R ∈ Q′ e todo a ∈ Σ,
iii. q′0 = E({q0}),
iv. F ′ = {R ∈ Q′|R conte´m um estado q ∈ F}.
(b) (1,5 pontos) Utilizando a construc¸a˜o do item (a), converta o seguinte AFN em um AFD
equivalente.
q1 q2 q3
a
b
a
ε
b
Resposta:
∅ {q1} {q2} {q3}
{q1, q2} {q2, q3} {q1, q3} {q1, q2, q3}
a
b
a
b
a,b
a,b
a
b
a
b
a,b
a,b
Os estados em cor azul sa˜o inalcanc¸a´veis desde o estado inicial e podem ser omitidos
junto com as transic¸o˜es correspondentes.
2. (1 ponto) Defina o que sa˜o estados n-equivalentes de um AFD.
Resposta: Seja o AFDM = (Q,Σ, δ, q0, F ). Dois estados q e q
′ sa˜o n-equivalentes se δ(q, a)
e δ(q′, a) sa˜o (n− 1)-equivalentes para todo a ∈ Σ. Dois estados q e q′ sa˜o 0-equivalentes se
ambos sa˜o estados de aceitac¸a˜o ou se nenhum deles e´ estado de aceitac¸a˜o.
3. (1 ponto) Desenhe o diagrama de estados de um AFN que reconhec¸a a linguagem descrita
pela expressa˜o regular (01 ∪ 1)∗.
Resposta:
q0 q0
q1 q2 q3
q4 q7
ε
ε
0 1
ε
0
ε
ε
4. (1 ponto) Determine uma expressa˜o regular para cada uma das seguintes linguagens sobre
o alfabeto {0, 1}.
(a) O conjunto de cadeias que comec¸am ou terminam com 00 ou 11.
Resposta: (00 ∪ 11)Σ∗ ∪ Σ∗(00 ∪ 11)
(b) O conjunto de cadeias que conte´m ambas as subcadeias 11 e 010.
Resposta: Σ∗11Σ∗010Σ∗ ∪ Σ∗010Σ∗11Σ∗
5. (2 pontos) Verdadeiro ou falso? Justifique suas respostas.
(a) Se L1 e´ regular e L2 na˜o e´ regular, enta˜o L1 ∪ L2 na˜o e´ regular.
Resposta: Falso. Considere a linguagem regular L1 = Σ
∗. Para qualquer linguagem
L2, regular ou na˜o, L1 ∪ L2 = Σ
∗.
(b) Se L1 e L2 sa˜o linguagens regulares, enta˜o L1 − L2 = {w|w ∈ L1 e w /∈ L2} e´ regular.
Resposta: Verdadeiro. Podemos escrever L1 − L2 = {w|w ∈ L1 e w ∈ L2} =
L1 ∩ L2. Sabemos que a classe das linguagens regulares e´ fechada sobre a interse-
c¸a˜o e a complementac¸a˜o, portanto, L1 − L2 e´ regular.
6. (2 pontos) As seguintes linguagens sa˜o regulares ou na˜o? Justifique suas respostas.
(a) L1 = {0
m1n|m,n ≥ 0 e m+ n = 8}.
Resposta: Regular. L1 conte´m somente cadeias de comprimento 8, portanto, e´ finita.
Toda linguagem finita e´ regular.
(b) L2 = {0
m1n|m,n ≥ 0 e m− n = 8}.
Resposta: Na˜o regular. Suponha L2 regular e seja p o comprimento de bombeamento.
Considere a cadeia de teste w = 0p+81p. Claramente, w ∈ L2 e |w| = 2p + 8 ≥ p,
portanto, pode ser subdividida na forma w = xyz conforme o lema do bombeamento.
Das condic¸o˜es do lema |y| > 0 e |xy| ≤ p obtemos y = 0k, com 1 ≤ k ≤ p. Se
bombeamos para baixo, obtemos a cadeia xy = 0p−k+81p. Esta cadeia na˜o pertence
a L2, pois a diferenc¸a entre as quantidades de 0s e 1s e´ 8 − k < 8, o que contradiz o
lema. Concluimos, enta˜o, que L2 na˜o e´ regular.