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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
1. (1.5 pontos) Seja w uma cadeia de uma linguagem L, com w 6= ε. Prove que, se L e´ livre-do-
contexto, enta˜o existe uma grama´tica livre-do-contexto que gera w em exatamente 2n − 1
passos, onde n = |w|. (Responda qual e´ essa grama´tica e prove que gera w na quantidade
de passos indicada).
Resposta: Se L e´ livre-do-contexto, enta˜o existe uma GLC que a gera, e que pode ser
colocada na forma normal de Chomsky. Uma grama´tica na forma de Chomsky gera qualquer
cadeia w ∈ L, com w 6= ε, em exatamente 2n− 1 passos, onde n = |w|. A grama´tica utiliza
n−1 aplicac¸o˜es de regras do tipo A→ BC para gerar n varia´veis a partir da varia´vel inicial,
e n aplicac¸o˜es de regras do tipo A→ a para converter as n varia´veis em terminais.
2. (1 ponto) Para todo nu´mero inteiro n ≥ 0, a linguagem Ln = {a
n
b
n
c
n} e´ livre-do-contexto?
Resposta: sim. Cada linguagem Ln conte´m uma u´nica cadeia: L0 = {ε}, L1 = {abc}, L2 =
{aabbcc}, . . . Uma GLC que gera Ln e´, simplesmente, S → a
n
b
n
c
n.
3. (1.5 pontos) Prove que a linguagem L = {0n
2
|n ≥ 0} na˜o e´ livre-do-contexto.
Resposta: Aplicamos o lema do bombeamento para LLCs. Suponha L livre-do-contexto,
e seja p seu comprimento de bombeamento. A cadeia s = 0p
2
∈ L possui comprimento
p2 ≥ p e, segundo o lema, pode ser bombeada. Fazemos s = uvxyz, com |vxy| ≤ p e
|vy| > 0. Assim, vy = 0q, onde 1 ≤ q ≤ p. Bombeando para cima, obtemos a cadeia
s′ = uv2xy2z = 0p
2+q. Esta cadeia pertence a L se e somente se seu comprimento e´ um
quadrado perfeito.
O comprimento de s′ e´ |s′| = p2 + q, e enta˜o
p2 + 1 ≤ |s′| ≤ p2 + p.
Por outro lado, p2 + p < p2 + p+ (p+ 1) = (p+ 1)2. Assim
p2 < |s′| < (p+ 1)2.
Por tanto, |s′| na˜o pode ser um quadrado perfeito e, enta˜o, s′ /∈ L. Isso contradiz o lema do
bombeamento, de onde concluimos que L na˜o e´ livre-do-contexto.
4. (1.5 pontos) Uma grama´tica regular e´ uma grama´tica livre-do-contexto G = (V,Σ, R, S)
na qual toda regra tem a forma A → ε ou A → aB, onde a e´ um terminal e A e B sa˜o
varia´veis. Suponha que a linguagem L e´ regular, e que o AFD M = (Q,Σ, δ, q0, F ) reconhece
L. Explique como construir uma grama´tica regular G que gere a mesma linguagem L.
Resposta: Vimos em aula como converter um AFD em uma GLC equivalente. Fazemos
V = Q e S = q0. Para cada transic¸a˜o δ(qi, a) = qj do AFD, adicionamos a regra de
substituic¸a˜o qi → aqj a` GLC. Para cada estado qi ∈ F , adicionamos a regra qi → ε.
5. (1 ponto) Seja o autoˆmato com pilha P = ({q0, q1}, {[, ]}, {A}, δ, q0, {q1}), onde δ e´ a func¸a˜o
de transic¸a˜o definida por
δ(q0, [, ε) = {(q0, A)}
δ(q0, ε, ε) = {(q1, ε)}
δ(q1, ], A) = {(q1, ε)}
δ(q, a, x) = ∅, para todo outro caso.
Qual a linguagem reconhecida pelo autoˆmato?
Resposta:
q0 q1
ε,ε→ ε
],A→ ε[,ε→ A
No estado inicial q0, o autoˆmato P empilha um A quando leˆ [. Na˜o determin´ısticamente,
muda ao estado de aceitac¸a˜o q1, onde desempilha A quando leˆ ]. Assim, P permanece no
seu estado de aceitac¸a˜o se para cada ] lido existe um A correspondente na pilha. Portanto,
P reconhece a linguagem L = {[m]n|m ≥ n ≥ 0}.
6. (1.5 pontos) Suponha que L1 e´ L2 sa˜o linguagens Turing-reconhec´ıveis e disjuntas (L1∩L2 =
∅). Suponha tambe´m que L1 ∪ L2 e´ Turing-reconhec´ıvel. Mostre que, enta˜o, L1 e L2 devem
ser ambas decid´ıveis. Para isso, descreva uma ma´quina de Turing que decide L1 (ou L2),
usando a forma
M= “Sobre a cadeia de entrada w:
1....
2....
...
Resposta: Se as linguagens L1, L2 e L1 ∪ L2 sa˜o Turing-reconhec´ıveis, enta˜o existem ma´-
quinas de Turing R1, R2 e R3 que as reconhecem, respectivamente. Uma cadeia w qualquer
pertence a L1, ou a L2, ou a nenhuma das duas linguagens. Neste u´ltimo caso, w pertence
a L1 ∪ L2. Podemos, enta˜o determinar a qual das treˆs linguagens w pertence rodando as
treˆs ma´quinas R1, R2 e R3 simulta´neamente, ja´ que alguma delas ira´ aceitar w. Assim, a
seguinte ma´quina de Turing decide L1.
D1= “Sobre a cadeia de entrada w:
1. Rode R1, R2 e R3 sobre w de forma alternada, um passo cada vez.
2. Se R1 aceita, aceite.
3. Se R2 ou R3 aceita, rejeite.
7. (0,5 ponto) Com uma ou duas frases, enuncie a tese de Church-Turing.
Resposta: Informalmente, a tese afirma que qualquer processo computacional que, intui-
tivamente, possa ser considerado um algoritmo, pode ser convertido a uma ma´quina de
Turing.
8. (1.5 pontos) Considere a seguinte ma´quina de Turing T . O alfabeto de entrada e´ {0, 1}.
q0
q1
q2
qaceita
qrejeita
0→ 0,D
1→ 1,D
⊔ → ⊔,D
0→ 0,D
⊔ → ⊔,D
1→ 1,D
⊔ → ⊔,D
0→ 0,D
1→ 1,D
(a) A ma´quina de Turing decide alguma linguagem? Se sua resposta e´ afirmativa, indique
qual a linguagem. Se sua resposta e´ negativa, explique por queˆ.
Resposta: a ma´quina “entra em loop” sobre a cadeia vazia e tambe´m sobre qualquer
cadeia que comec¸a com 1, portanto, na˜o decide nenhuma linguagem.
(b) Qual a linguagem L reconhecida pela ma´quina de Turing?
Resposta: a ma´quina chega ao estado de aceitac¸a˜o se recebe como entrada a cadeia 0
ou qualquer cadeia que comec¸a com 00. Portanto, reconhece a linguagem L = 0∪00Σ∗.
(c) A linguagem L do item (b) e´, obviamente, Turing-reconhec´ıvel. E´, tambe´m, decid´ıvel?
Resposta: a linguagem L e´ decid´ıvel. Por exemplo, a seguinte ma´quina de Turing a
decide:
q0
q1
qaceita
qrejeita
0→ 0,D
1→ 1,D
⊔ → ⊔,D
0→ 0,D
⊔ → ⊔,D
1→ 1,D