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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
1. Considere o seguinte autoˆmato finito na˜o determin´ıstico (AFN) sobre o alfabeto Σ = {a,b}.
q0 q1 q2
a,b
a b
a
a
b
(a) (1 ponto) Transforme o AFN em um autoˆmato finito determin´ıstico (AFD) equivalente.
Utilize o me´todo visto em aula, e nomeie cada estado do AFD apropriadamente para
indicar a quais estados do AFN corresponde. Atenc¸a˜o: Na˜o e´ necessa´rio mostrar os
estados inalcanc¸a´veis desde o estado inicial.
Resposta:
Q0
Q01 Q012
Q1 Q2
a
b
a
b
a
b
a
b
a
b
(Notac¸a˜o: Qij = {qi, qj})
(b) (1 ponto) Transforme o AFN em um autoˆmato finito na˜o determin´ıstico generalizado
(AFNG) equivalente.
Resposta:
qi q0 q1 q2 qf
a ∪ bε
a b
a
a
b
ε
(c) (1 ponto) A partir do AFNG do item (b), obtenha uma expressa˜o regular para a lin-
guagem reconhecida pelo autoˆmato. Utilize o me´todo visto em aula (mostre todos os
passos).
Resposta: eliminando os estados intermedia´rios q2, q1 e q0, nessa ordem, obtemos
qi q0 q1 qf
a ∪ bε
a b ∪ aa
ab
ε
qi q0 qf
(a ∪ b)(b ∪ aa)∗ε
a ∪ (a ∪ b)(b ∪ aa)∗ab
qi qf
[a ∪ (a ∪ b)(b ∪ aa)∗ab]∗(a ∪ b)(b ∪ aa)∗
Portanto, uma expressa˜o regular que gera a linguagem reconhecida pelo autoˆmato e´
[a ∪ (a ∪ b)(b ∪ aa)∗ab]∗(a ∪ b)(b ∪ aa)∗
(d) (1 ponto) Construa um grama´tica livre-do-contexto GLC que gere a mesma linguagem
reconhecida pelo autoˆmato. Utilize o me´todo visto em aula.
Resposta: a partir do AFD obtido no item (a), obtemos a grama´tica
Q0 → aQ01 | bQ1
Q1 → aQ2 | bQ1 | ε
Q2 → aQ1 | bQ0
Q01 → aQ012 | bQ1 | ε
Q012 → aQ012 | bQ01 | ε
2. (1 ponto) Desenhe um autoˆmato finito que reconhec¸a o complemento da linguagem reco-
nhecida pelo seguinte AFN. Explique seu racioc´ınio. Considere o alfabeto Σ = {0,1}.
0 0,1
Resposta: Primeiro, transformamos o AFN em um AFD equivalente. Podemos fazer
isso facilmente adicionando um estado e colocando as transic¸o˜es que faltam, da seguinte
forma:
0 0,1
1
0,1
0,1
Queremos um autoˆmato que aceite as palavras que na˜o sa˜o aceitas pelo AFD acima, e
que sim aceite aquelas que o AFD na˜o aceita. Para isso, simplesmente permutamos os
estados de aceitac¸a˜o pelos de nao-aceitac¸a˜o, e obtemos
0 0,1
1
0,1
0,1
3. (1 ponto) Seja Σ um alfabeto com a ∈ Σ, e L uma linguagem regular sobre Σ. Prove que a
linguagem L′ = {w|w = w1w2, onde w1,w2 ∈ L e w tem pelo menos dois a’s} e´ regular.
Resposta: A linguagem L′ e´ a intersec¸a˜o de duas linguagens, L1 = {w1w2|w1,w2 ∈ L}
e L2 = {w|w tem pelo menos dois a’s}. A linguagem L1 e´ a concatenac¸a˜o da linguagem
regular L com L e, portanto, e´ regular, pois a classe das linguagens regulares e´ fechada
sobre a concatenac¸a˜o. A linguagem L2 tambe´m e´ regular, pois pode ser descrita pela
expressa˜o regular Σ∗aΣ∗aΣ∗. Sabemos que a classe das linguagens regulares tambe´m
e´ fechada sobre a intersec¸a˜o (vimos em aula como construir um AFD que reconhec¸a a
intersec¸a˜o de duas linguagens regulares) e, portanto, L′ = L1 ∩ L2 e´ regular.
4. (2 pontos) Prove que as seguintes linguagens na˜o sa˜o regulares.
(a) L2 = {a
ibjck| i, j, k ≥ 0 e i2 + j2 = k2}.
Resposta: Suponha que L2 seja regular, e que p seja o comprimento de bombea-
mento. Considere w = a3pb4pc5p. Note que (5p)2 = (3p)2 + (4p)2, portanto w ∈ L2,
e |w| ≥ p. Fazemos w = xyz, onde |xy| ≤ p e |y| > 0. Enta˜o, xy = am, com m ≤ p,
e y = an, com 0 < n ≤ m. Segundo o lema do bombeamento, xz ∈ L2. No entanto,
xz = a3p−nb4pc5p, e (5p)2 6= (3p − n)2 + (4p)2. Enta˜o, xz /∈ L2. A contradic¸a˜o
implica que L2 na˜o e´ regular.
(b) L3 = {xw| x,w ∈ {0,1}
∗ e |x| = |w|}. Questa˜o anulada
5. Verdadeiro ou falso? Justifique (prove) suas repostas
(a) (1 ponto) A classe das linguagens regulares e´ fechada sobre a operac¸a˜o Impar(L) =
{w|w ∈ L e |w| e´ impar}.
Resposta: Verdadeiro. A linguagem L′ = {w| |w| e´ impar} e´ regular, pois pode
ser descrita pela expressa˜o regular Σ(ΣΣ)∗, onde Σ e´ o alfabeto. A linguagem
Impar(L) e´ a intersec¸a˜o das linguagens L e L′. Sabemos que a classe das linguagens
regulares e´ fechada sobre a intersec¸a˜o, portanto, L e´ regular.
(b) (1 ponto) Seja a linguagem L gerada pela expressa˜o a∗b∗. Qualquer AFD que reconhec¸a
L deve ter pelo menos dois estados de aceitac¸a˜o.
Resposta: Verdadeiro. SejaM = (Q,Σ, δ, q0, F ) um AFD qualquer que reconhec¸e
L. A cadeia vazia ε ∈ L, portanto, o estado inicial q0 dedeve ser um estado de
aceitac¸a˜o. Considere agora a cadeia ab. O AFD deve aceitar essa cadeia, portanto,
existem estados qa e qb tais que δ(q0, a) = qa, δ(qa, b) = qb e qb e´ um estado de
aceitac¸a˜o. A questa˜o e´: o estado qb pode ser o mesmo estado q0, ou necessariamente
deve ser um estado diferente? Suponha que qb = q0, e considere a cadeia abab. Ao
ler essa cadeia, o autoˆmato passa pela sequeˆncia de estados q0qaq0qaq0 e a aceita. No
entanto, abab /∈ L, o que produz uma contradic¸a˜o. Enta˜o, os estados de aceitac¸a˜o
q0 e qb devem ser diferentes.