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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
1. (2 pontos) Seja G = (V,Σ,R,S) uma grama´tica livre-do-contexto que gera a linguagem L, e
b o nu´mero ma´ximo de s´ımbolos no lado direito de uma regra. Considere uma cadeia w ∈ L.
Mostre que, se |w| ≥ b|V | +1, enta˜o em qualquer a´rvore sinta´tica para w existe um caminho
da raiz (varia´vel inicial) para uma folha (terminal) no qual alguma varia´vel aparece mais de
uma vez.
Resposta: Em qualquer a´rvore sinta´tica, a quantidade de folhas (varia´veis e terminais)
a um passo da var´ıa´vel inicial e´ menor ou igual a b; a dois passos da varia´vel inicial, e´
menor ou igual a b2, e a n passos, e´ menor ou igual a bn. Assim, uma a´rvore de altura
n gera uma cadeia w de comprimento |w| ≤ bn. Tambe´m podemos afirmar que, se uma
cadeia tem comprimento |w| ≥ bn + 1, a altura da a´rvore devera´ ser pelo menos n + 1.
Substituindo b = |V |, concluimos que, se |w| ≥ b|V | + 1, enta˜o qualquer a´rvore sinta´tica
tera´ uma altura de, pelo menos, |V |+1. Isto significa que existe um caminho da varia´vel
inicial a um terminal com |V | + 2 s´ımbolos (incluindo tanto a varia´vel inicial quanto o
terminal). Nesse conjunto de s´ımbolos, existe um terminal e |V | + 1 varia´veis. Como a
quantidade total de varia´veis em G e´ |V |, enta˜o, ao longo do caminho, pelo menos uma
delas deve estar repetida.
2. (2 pontos) Desenhe o diagrama de estados de um autoˆmato com pilha que reconhec¸a a
linguagem {aibjcjbkai+k| i, j, k ≥ 0}. Para receber pontos por esta questa˜o, o autoˆmato na˜o
podera´ conter mais de 8 estados.
Resposta:
q0 q1 q2 q3 q4
q5q6
ε,ε → $
a,ε → x
ε,ε → ε
b,ε → y
ε,ε → ε
c,y→ ε
ε,ε → ε
b,ε → x
ε,ε → ε
a,x→ ε
ε,$→ ε
3. (1 ponto) Suponha que L e´ uma linguagem Turing-reconhec´ıvel sobre um alfabeto Σ, e que
M e´ uma ma´quina de Turing que reconhece L. Queremos construir um enumerador E para
L. Por que na˜o podemos usar o seguinte algoritmo para E?
E= “Ignore a entrada:
1. Repita os seguintes passos para i = 1, 2, 3, . . .
2. Gere uma cadeia si ∈ Σ
∗ (suponha que s1, s2, s3, . . . e´ uma lista de todas
as cadeias poss´ıveis em Σ∗).
3. Rode M sobre si.
4. Se M aceita, imprima si.”
Resposta: Na˜o podemos, porque M pode “entrar em loop”, no passo 3, sobre uma
cadeia si. Se isso acontece, enta˜o o enumerador na˜o ira´ verificar as cadeias seguintes a si
e, consequentemente, na˜o imprimira´ mais cadeias de L.
4. (2 pontos) Seja A = {〈R,S〉| R e S sa˜o expresso˜es regulares e L(R) ⊆ L(S)}. Prove que A
e´ decid´ıvel. Na sua prova, descreva uma ma´quina de Turing que decide A, no formato
M= “Sobre a entrada 〈R,S〉, onde R e S sa˜o expresso˜es regulares:
1....
2....
...
n. Se... aceite; se... rejeite.”
Pode utilizar, como subprogramas, as ma´quinas de Turing que decidem AAFD, AAFN, AEXR,
VAFD e EQAFD, vistas em aula.
Resposta: Note que L(R) ⊆ L(S) se e somente se L(R) ∩ L(S) = ∅. Enta˜o podemos
decidir A testando vacuidade, como no seguinte algoritmo.
M= “Sobre a entrada 〈R,S〉, onde R e S sa˜o expresso˜es regulares:
1. Construa um autoˆmato finito determin´ıstico D tal que
L(D) = L(R) ∩ L(S). E´ poss´ıvel fazer isso, pois a classe das linguagens
regulares e´ fechada sobre a complementac¸a˜o e a intersec¸a˜o.
2. Rode a ma´quina de Turing T que decide VAFD sobre 〈D〉.
3. Se T aceita, aceite; se T rejeita, rejeite.”
5. (1 ponto) O conjunto de linguagens regulares sobre um alfabeto Σ e´ conta´vel? Justifique
sua resposta.
Resposta: Sim. Para cada linguagem regular, podemos construir um autoˆmato finito
determin´ıstico (AFD) que o reconhece. Todo AFD possui uma descric¸a˜o finita, que pode
ser codificada como uma cadeia sobre um alfabeto, por exemplo, {0, 1}. As cadeias sobre
{0, 1} que sa˜o representac¸o˜es va´lidas de um AFD podem ser listadas em ordem lexico-
gra´fica, portanto, a quantidade de cadeias e´ conta´vel. Como existe uma correspondeˆncia
entre linguagens regulares e cadeias que representam AFDs, concluimos que a quantidade
de linguagens regulares tambe´m e´ conta´vel.
6. (1 ponto) Se uma linguagem L e´ livre-do-contexto enta˜o L e´ decid´ıvel? Justifique sua
resposta.
Resposta: Sim. Toda linguagem livre-do-contexto e´ decid´ıvel, e o complemento de uma
linguagem decid´ıvel tambe´m e´ decid´ıvel. Se uma ma´quina de Turing M decide uma
linguagem L, enta˜o podemos decidir se uma cadeia w ∈ L rodando M sobre w. Se M
aceita w, enta˜o w /∈ L, e se M rejeita w, enta˜o w ∈ L.
7. (1 ponto) Descreva um algoritmo para decidir se uma grama´tica livre-do-contexto gera a
cadeia vazia. Utilize um formato similar ao da questa˜o 4.
Resposta:
M= “Sobre a entrada 〈G〉, onde G e´ uma grama´tica livre-do-contexto:
1. Converta G para uma grama´tica equivalente na forma normal de Chomsky.
2. Liste todas as derivac¸o˜es com um passo.
3. Se alguma dessas derivac¸o˜es gera ε, aceite; se na˜o, rejeite.”