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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
Prof. Jorge C. Lucero
25 de maio de 2015
Nome: Matr´ıcula:
1. (a) Desenhe o diagrama de estados de um autoˆmato com pilha AP que reconhec¸a a lingua-
gem L = {w|w ∈ {a, b}∗ e w e´ um pal´ındromo de comprimento ı´mpar}.
Resposta:
q0 q1 q2 q3
ε, ε→ $
a, ε→ a
b, ε→ b
b, ε→ ε
a, ε→ ε
a, a→ ε
b, b→ ε
ε, $→ ε
(b) Fornec¸a a definic¸a˜o formal do AP anterior. Na˜o esquec¸a de definir a func¸a˜o de transic¸a˜o.
Resposta: P = (Q,Σ,Γ, δ, q0, {q3}), ondeQ = {q0, q1, q2, q3}, Σ = {a, b}, Γ = {a, b, $}
e δ e´ a func¸a˜o Q× Σε × Γε → P(Q× Γε) definida por
δ(q0, ε, ε) = {(q1, $)}
δ(q1, x, ε) = {(q1, x),(q2, ε)}, para x = a ou x = b
δ(q2, x, x) = {(q2, ε)}, para x = a ou x = b
δ(q2, ε, $) = {(q3, ε)}
δ(q, x,y) = ∅, para qualquer outro caso
2. Determine se as seguintes linguagens sa˜o livres-do-contexto ou na˜o. Prove (formalmente)
sua resposta.
(a) L1 = {w|w ∈ {a, b}
∗, o comprimento de w e´ par e a primeira metade de w conte´m
somente as}.
Resposta: L1 e´ livre-do-contexto. A seguinte GLC gera L1 : S → aSa | aSb | ε.
(b) L2 = {a
nbnck|n, k ≥ 0 e k ≤ n}.
Resposta: L2 na˜o e´ livre-do-contexto. A prova utiliza o lema do bombeamento:
Suponha que L2 seja livre-do-contexto com comprimento de bombeamento p. Escolha
a cadeia de teste s = apbpcp. Note que s ∈ L2, e |s| = 3p ≥ p. Fac¸a s = uvxyz, com
|vxy| ≤ p e |vy| > 0. Existem as seguintes duas possibilidades para vy:
i. Se vy conte´m k as e ℓ bs, com 1 ≤ k + ℓ ≤ p, enta˜o, uv0xy0z = ap−kbp−ℓcp /∈ L2,
pois a quantidade de as ou a quantidade de bs (ou ambas) sa˜o menores que a
quantidade de cs.
ii. Se vy conte´m k bs e ℓ bs, com 1 ≤ k + ℓ ≤ p, enta˜o, uv2xy2z = apbp+kcp+ℓ /∈ L2,
pois a quantidade de bs ou a quantidade de cs (ou ambas) sa˜o maiores que a
quantidade de as.
Conclu´ımos que L2 viola o lema do bombeamento, o que implica que na˜o e´ livre-do-
contexto.
3. Seja uma LLC L gerada por uma grama´tica G = (V,Σ, R, S), e seja b o comprimento ma´ximo
das cadeias no lado direito das regras de substituic¸a˜o. Seja tambe´m w ∈ L uma cadeia de
comprimento |w| ≥ p, com p = b|V |+1. Considere b ≥ 2 e prove que a altura da a´rvore
sinta´tica associada a w e´ maior que |V |. Explique claramente seu racioc´ınio.
Resposta: Em qualquer a´rvore sinta´tica para w, a n passos da varia´vel inicial ha´, no
ma´ximo, bn folhas. Portanto, se a altura da a´rvore sinta´tica e´ h ≤ n, enta˜o |w| ≤ bn.
Reciprocamente, |w| > bn ⇒ h > n. Por outro lado, temos que b|V |+1 = b · b|V | > b|V | (pois
b > 1). Assim, se |w| ≥ b|V |+1 enta˜o |w| > b|V | e, pela implicac¸a˜o anterior, h > |V |.
4. Descreva uma ma´quina de Turing (de uma fita, determin´ıstica) que decida a linguagem do
item 2(b), na forma:
M= “Sobre a cadeia de entrada . . .:
1....
2....
...
Explique claramente como e´ realizado cada passo.
Resposta:
M= “Sobre a cadeia de entrada w:
1. Fac¸a uma varredura sobre a cadeia de entrada, de esquerda a direita, para
determinar se e´ membro de a∗b∗c∗ e rejeite se na˜o for.
2. Ate´ esgotar todos os as na˜o marcados, repita os seguintes passos:
3. Marque um a na˜o marcado.
4. Desloque a cabec¸a a` direita para marcar um b na˜o marcado. Se
nenhum for encontrado, rejeite.
5. Desloque a cabec¸a a` direita para marcar um c na˜o marcado. Se
nenhum for encontrado, continue.
6. Fac¸a uma varredura para determinar se existe algum b ou c na˜o marcado.
No caso afirmativo, rejeite.
7. Aceite.”
5. Prove que uma linguagem e´ decid´ıvel se e somente se e´ enumera´vel em ordem lexicogra´fica.
Resposta:
Suponha L decid´ıvel e seja D a MT que a decide. Enta˜o, a seguinte MT enumera L em
ordem lexicogra´fica:
E= “Ignore a entrada:
1. Gere cadeias s1, s2, s3, . . . sobre Σ em ordem lexicogra´fica. A cada cadeia
gerada si:
2. Rode D sobre si. Se aceita, imprima si.”
Suponha L enumera´vel em ordem lexicogra´fica e seja E a MT enumeradora. Enta˜o, a
seguinte MT decide L:
D= “Sobre a cadeia de entrada w:
1. Rode E para gerar cadeias s1, s2, s3, . . . ∈ L. A cada cadeia gerada si:
2. Compare w e si. Se w = si, aceite; se w < si, rejeite.”
6. Suponha que os conjuntos A1, A2, . . . , Ak formam uma partic¸a˜o de Σ
∗ (onde Σ e´ um alfa-
beto); isto e´, sua unia˜o e´ Σ∗ e quaisquer dois deles sa˜o disjuntos. Prove que se todos os Ai
sa˜o Turing-reconhec´ıveis enta˜o tambe´m sa˜o decid´ıveis.
Resposta:
Sejam R1, R2, . . . , Rk as respectivas MTs que reconhecem A1, A2, . . . , Ak. Enta˜o, a seguinte
MT decide Ai:
Di= “Sobre a cadeia de entrada w:
1. Rode R1, R2, . . . , Rk sobre w de forma alternada, um passo cada vez.
2. Se Ri aceita, aceite.
3. Se alguma Rj 6= Ri aceita, rejeite.”
Cada item vale 1,25 pontos.