Exercícios sobre decidibilidade do 1º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 5
O conjunto de todos os autoˆmatos com pilha na˜o-determin´ısticos e´ conta´vel ou inconta´vel? Se
for conta´vel, mostre como construir uma correspondeˆncia com o conjunto dos nu´meros naturais.
Se for inconta´vel, mostre que e´ imposs´ıvel contruir essa correspondeˆncia, fazendo uma prova por
diagonalizac¸a˜o.
Resposta: O conjunto e´ conta´vel. Cada AP na˜o-determin´ıstico A pode ser descrito por uma
cadeia 〈A〉 sobre um alfabeto Σ. O conjunto P de todas as cadeias 〈A〉 que decrevem APs
na˜o-determin´ısticos pode ser enumerado em ordem lexicogra´fica. Por exemplo, a seguinte MT
enumera P
E= “Ignore a entrada:
1. Repita os seguintes passos para i = 1, 2, 3, . . .
2. Gere uma cadeia si ∈ Σ
∗, em ordem lexicogra´fica (comec¸ando por
s1 = ε, em cada passo i compute o sucessor lexicogra´fico da cadeia
gerada no passo i− 1 anterior).
3. Verifique se si e´ uma descric¸a˜o va´lida de um AP na˜o-determin´ıstico. No caso
afirmativo, imprima si.”
Seja 〈A1〉, 〈A2〉, 〈A3〉, . . . a lista de descric¸o˜es de APs gerada pelo enumerador E. Enta˜o, existe
uma correspondeˆncia f entre entre o conjunto de todos os APs e o conjunto dos nu´meros
naturais, definida simplesmente por f(n) = An.
Considere o problema de determinar se as linguagens de dois autoˆmatos finitos determin´ısticos
dados sa˜o complemento uma da outra. Formule o problema como uma linguagem e prove que e´
decid´ıvel. Na sua prova, pode utilizar qualquer teorema sobre linguagens decid´ıveis visto em aula.
Resposta: O problema pode ser representado pela linguagem T = {〈M,N〉|M e N sa˜o
AFDs e L(M) = L(N)}. Para provar sua decibilidade, aplicamos o Teorema que afirma que a
linguagem EQAFD = {〈M,N〉|M e N sa˜o AFDs e L(M) = L(N)} e´ decid´ıvel. Seja S a MT
que decide EQAFD. A seguinte MT decide T :
D= “Sobre a entrada 〈M,N〉, onde M e N sa˜o AFDs :
1. Construa um AFD O que reconhec¸a a linguagem L(N). Para isso, troque os
estados de aceitac¸a˜o de N por estados de na˜o-aceitac¸a˜o e vice versa.
2. Rode S sobre 〈M,O〉. Se S aceita, aceite; se S rejeita, rejeite.”
Considere a seguinte afirmac¸a˜o: se L e´ uma linguagem decid´ıvel e L′ ⊆ L, enta˜o L′ tambe´m
e´ uma linguagem decid´ıvel. Se a afirmac¸a˜o for verdadeira, prove-a. Se for falsa, fornec¸a um
contra-exemplo.
Resposta: A afirmc¸a˜o e´ falsa. Como contra-exemplo, considere L = Σ∗. Enta˜o, L e´ regular e,
portanto, decid´ıvel. No entanto, note que L conte´m todas as cadeias sobre Σ, e qualquer outra
linguagem sobre Σ estara´ contida em L, incluindo as linguagens indecid´ıveis. Por exemplo, fac¸a
L′ = AMT = {〈M,w〉|M e´ uma MT que aceita w}, onde a codificac¸a˜o para M,w e´ realizada
sobre Σ (i.e., 〈M,w〉 ∈ Σ∗). Assim, L′ ⊆ L, e L′ e´ indecid´ıvel
Considere o problema de determinar se uma expressa˜o regular sobre o alfabeto Σ = {0, 1} descreve
uma linguagem que conte´m alguma cadeia que comec¸a com 11 e termina com 0. Formule o
problema como uma linguagem e prove que e´ decid´ıvel. Na sua prova, pode utilizar qualquer
teorema sobre linguagens decid´ıveis visto em aula.
Resposta: O problema pode ser representado pela linguagem T = {〈R〉|R e´ uma expressa˜o
regular sobre {0, 1} e 11x0 ∈ L(R) para algum x ∈ Σ∗}. Para provar sua decibilidade,
aplicamos o Teorema que afirma que a linguagem VAFD = {〈M〉|M e´ um AFD e L(M) = ∅} e´
decid´ıvel. Seja S a MT que decide VAFD. A seguinte MT decide T :
D= “Sobre a entrada 〈R〉, onde R e´ uma expressa˜o regular:
1. Transforme R em um AFN equivalente, e logo transforme este AFN em um AFD
A equivalente (vimos em aula como fazer ambas transformac¸o˜es).
2. Transforme a expressa˜o regular 11Σ∗0 em um AFN equivalente, e logo transforme
este AFN em um AFD B equivalente.
3. Construa um AFD C que reconhec¸a a linguagem L(A) ∩ (B).
4. Rode S sobre 〈C〉. Se S aceita, rejeite; se S rejeita, aceite.”