Buscar

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

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
1. Defina formalmente:
(a) (0,25 ponto) Alfabeto
Resposta: qualquer conjunto finito e na˜o vazio.
(b) (0,25 ponto) Cadeia
Resposta: qualquer sequeˆncia finita de elementos (s´ımbolos) de um alfabeto.
(c) (0,25 ponto) Linguagem
Resposta: qualquer conjunto de cadeias.
(d) (1,25 pontos) Expressa˜o regular
Resposta: uma expressa˜o regular sobre uma alfabeto Σ e´: (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(4) R∗1, onde R1 e´ uma expressa˜o regular.
2. (1,5 ponto) Prove que a linguagem L = {anbabc2n|n > 0} na˜o e´ regular. Utilize o Lema do
bombeamento.
Resposta: Suponha L regular, e seja p seu comprimento de bombeamento. Considere a
cadeia w = apbabc2p. Assim, w ∈ L e |w| = 3p + 3 ≥ p. Dividimos w na forma w = xyz.
As condic¸o˜es |xy| ≤ p e |y| > 0 implicam que y esta´ contido na sequeˆncia inicial de as e que
y = ak, com 0 < k ≤ p. Enta˜o, xyyz = ap+kbabc2p. Nesta cadeia, a quantidade de cs (2p)
na˜o e´ igual ao duplo da quantidade da as (p+ k) na sequeˆncia inicial, portanto, xyyz /∈ L.
Concluimos que L na˜o satisfaz o Lema e enta˜o deve ser na˜o regular.
3. (1,5 pontos) A diferenc¸a entre dois conjuntos A e B e´ definida como A − B = {x| x ∈
A e x /∈ B}. Se L1 e L2 sa˜o linguagens regulares, enta˜o L1 − L2 sempre e´ regular? Prove
sua resposta.
Resposta: note que L1 − L2 = {x| x ∈ L1 e x /∈ L2} = L1 ∩ L2. A classe das linguagens
regulares e´ fechada sobre as operac¸o˜es de intersec¸a˜o e complementac¸a˜o, portanto, L1 − L2
sempre e´ regular.
4. Seja a seguinte linguagem
TRIPLES = {a3n|n ≥ 0}
(a) (1 ponto) Fornec¸a uma expressa˜o regular para TRIPLES
Resposta: (aaa)∗.
(b) (0,5 ponto) Considere agora a seguinte prova de que TRIPLES na˜o e´ regular:
i. Suponha TRIPLES regular. Enta˜o, TRIPLES satisfaz o lema do bombeamento;
seja p seu comprimento de bombeamento.
ii. Escolha a cadeia de teste w = xyz = a3p.
iii. O lema do bombeamento exige |xy| ≤ p e |y| > 0. Fac¸a, enta˜o, y = a.
iv. Enta˜o, xy2z = a3p+1.
v. 3p + 1 na˜o e´ mu´ltiplo de 3, enta˜o xy2z /∈ TRIPLES. Portanto, TRIPLES na˜o
satisfaz o lema do bombeamento.
vi. A contradic¸a˜o implica que TRIPLES na˜o e´ regular.
Claramente, esta prova contradiz o item (a). O que esta´ errado?
Resposta: A prova na˜o considera todas as poss´ıveis subdiviso˜es da cadeia de teste.
(c) (0,5 ponto) Qual o comprimento mı´nimo de bombeamento de TRIPLES? Justifique
sua resposta.
Resposta: O comprimento mı´nimo e´ 1. Se w e´ uma cadeia de TRIPLES e |w| ≥ 1,
enta˜o w = a3n, com n ≥ 1, e pode ser bombeada fazendo x = ε, y = aaa e z igual ao
restante da cadeia. A cadeia vazia na˜o pode ser bombeada, pois na˜o poderia satisfazer
|y| > 0.
5. (1 ponto) A expressa˜o regular Σ+@Σ+.Σ+, onde Σ conte´m todas as letras do alfabeto,
descreve enderec¸os de e-mail da forma john@something.something. Desenhe o diagrama de
estados de um autoˆmato finito na˜o determin´ıstico que reconhec¸a a linguagem descrita por
essa expressa˜o. Nos ro´tulos das transic¸o˜es do autoˆmato, pode usar o s´ımbolo Σ para indicar
qualquer s´ımbolo do alfabeto. Note que os s´ımbolos @ e . na˜o pertencem a Σ.
Resposta:
q0 q1 q2 q3 q4 q5
Σ
Σ @ Σ
Σ
. Σ
Σ
6. (2 pontos) Prove que para todo AFN existe um AFD equivalente. Na sua prova, considere
somente o caso de AFNs sem transic¸o˜es-ε.
Resposta: A prova e´ por construc¸a˜o. Seja um AFN N = (Q,Σ, δ, q0, F ) sem transic¸o˜es-ε.
Constru´ımos um AFD equivalente M = (Q′,Σ, δ′, q′0, F
′) fazendo:
Q′ = P(Q),
δ′(R,a) =
⋃
r∈R
δ(r,a), para R ∈ Q′ e a ∈ Σ,
q′0 = {q0},
F ′ = {R|R ∈ Q′ e R conte´m um estado de aceitac¸a˜o de N}

Outros materiais