gabarito-p2 2013.2

Prévia do material em texto

P2 — Linguagens Formais e Teoria da Computac¸a˜o, 2013.2
Prof. Christiano Braga
Instituto de Computac¸a˜o
Universidade Federal Fluminense
11/12/2013
Gabarito
1. Considere a grama´tica para expresso˜es aritme´ticas G = ({E, T, F}, {+, ∗, [, ], x}, P, E) com
P = {E → T | E + T, T → F | T ∗ F, F → [E] | x}.
Responda: (a) (1,0 ponto) Por que esta grama´tica na˜o e´ amb´ıgua?
Resposta: Uma grama´tica livre de contexto e´ amb´ıgua se existe pelo menos uma palavra que
possui duas ou mais derivac¸o˜es a` esquerda ou a direita. Intuitivamente, adic¸o˜es da˜o origem a
T ermos e multiplicac¸o˜es a Fatores. Formalmente, a prova e´ por induc¸a˜o estrutural no tamanho de
uma palavra gerada por G. A t´ıtulo de exemplo, a palavra x ∗ x + x tem a a´rvore de derivac¸a˜o a
seguir.
E
�� ��
E
��
+ T
��
T
�� ��
F
��
T
��
∗ F
��
x
F
��
x
x
Se escolhessemos E → T como primeira derivac¸a˜o, T → T ∗ F viria em seguida. De T e´ poss´ıvel
gerar x mas de F na˜o e´ poss´ıvel gerar uma adic¸a˜o sem colchetes.
(b) (2 pontos) Aplique o algoritmo de Earley para verificar se a palavra x ∗x+x e´ gerada por
G.
Resposta:
D0 =
E → •T/0
E → •E + T/0
T → •F/0
T → •T ∗ F/0
F → •[E]/0
F → •x/0
Conjunto de produc¸o˜es incial.
D1 =
F → x • /0
T → F • /0
T → T • ∗F/0
E → T • /0
E → E •+T/0
(x ∗ x + x)
D2 =
T → T ∗ •F/0
F → •[E]/2
F → •x/2
(x ∗ x + x)
D3 =
F → x • /2
T → T ∗ F • /0
E → T • /0
E → T • ∗F/0
E → E •+T/0
(x ∗ x + x)
D4 =
E → E + •T/0
T → •F/4
T → •T ∗ F/4
F → •[E]/4
F → •x/4
(x ∗ x + x)
D5 =
F → x • /4
T → F • /4
T → T • ∗F/4
E → E + T • /0
(x ∗ x + x)
2. (3 pontos) Descreva uma ma´quina de Turing que reconhec¸a a linguagem
L = {anbncn | n ≥ 0}.
Resposta:
// q0
(β,β,D)
��
(I,I,D)
��
(a,A,D) //
(B,B,D)
��
q1
(a, a,D),
(B,B,D)
TT
(b,B,D) // q2
(b, b,D),
(C,C,D)
TT
(c,C,E) // q3
(A,A,D)
xx
(a, a, E),
(b, b, E),
(B,B,E),
(C,C,E)
TT
q4
(B,B,D)
TT
(C,C,D)
��
q5
(C,C,D)
TT
(β,β,D)
��
q6
O s´ımbolo I denota o in´ıcio da fita.
3. (1 ponto) Qual e´ a tese (ou hipo´tese) de Church-Turing?
Resposta: A capacidade de computac¸a˜o representada pela ma´quina de Turing e´ o limite ma´ximo
que pode ser atingido por qualquer dispositivo de computac¸a˜o.
2
4. (3 pontos) Por que existem mais problemas do que algoritmos para resolveˆ-los?
Resposta: Pela tese de Church-Turing, e´ algoritmico o problema, isto e´, a linguagem reconhecida
por uma ma´quina de Turing. Existe, pelo menos, uma linguagem que na˜o e´ reconhecida por uma
ma´quina de Turing, a linguagem na˜o-recursivamente enumera´vel L = {Xi | Xi 6∈ ACEITA(Ti)}
onde Xi e´ a codificac¸a˜o lexicogra´fica da ma´quina de Turing Ti.
De fato, o conjunto de todas as ma´quinas de Turing e´ isomorfo a um subconjunto dos nu´meros
naturais, dado pela ordenac¸a˜o lexicogra´fica que inclui Xi. Logo, infinito pore´m enumera´vel, como os
Naturais. No entanto, o conjunto das linguagens na˜o-recursivamente enumera´veis (isto e´, de todos
os problemas indecid´ıveis) e´ tambe´m infinito pore´m na˜o e´ enumera´vel. O cardinal do conjunto dos
problemas indecid´ıveis e´ maior do que o do conjunto dos problemas decid´ıveis, isto e´, reconhec´ıveis
por uma ma´quina de Turing, uma vez que o cardinal dos Naturais e´ o menor cardinal dentre os
conjuntos infinitos, em particular, daqueles na˜o-conta´veis.
3