Universidade Federal da Paraíba
Programa de Pós-Graduação em Informática
Teoria da Computação – 2013.1
4 - DECIDIBILIDADE
SIPSER – Exercícios
Equipe: Dorgival Netto, Jarbele Cássia, Silvia Azevedo
{dorgidetto, jarbele.cassia}@gmail.com, [email protected]
2
Relembrando o conceito de Decidibilidade...
• Um problema é decidível se sua solução é encontrada num
tempo finito, ou seja, existe uma Máquina de Turing que
retorna uma resposta. Caso contrário, ele é indecidível. O
conceito de decidibilidade não trata a quantidade de tempos
gasto e sim se ele é finito.
• Se o problema pode ser representado por uma linguagem
recursiva (onde a Máquina de Turing sempre pára) então o
problema é decidível.
3
Relembrando o conceito de Decidibilidade...
Decidível
Não-decidível
Parcialmente
Decidível
Completamente
Insolúveis
Computável
Não Computável
4
Exercícios
5
4.2. Considere o problema de se determinar se um AFD
e uma expressão regular são equivalentes. Expresse
esse problema como uma linguagem e mostre que ele é
decidível.
Resposta:
Como EQ AFD, EXR ={(A,R) / A é um AFD, R é uma expressão regular
e L(A) = L(R)}. Mostre que MT E decide EQ AFD, EXR .
E = Sobre a entrada (A,R); onde E é uma MT:
1.Converta a expressão regular R para um AFD B, equivalente
utilizando o procedimento indicado no teorema 1.28.
2. Use a MT C para decidir EQ AFD indicado no teorema 4.5, com a
entrada (A,B).
3. Se R aceita, aceite. Se R rejeita, rejeite.
6
4.3. Seja TODAS AFD = {(A) / A é um AFD e L(A) = Σ*}.
Mostre que a MT L decide TODASAFD.
Resposta:
Como TODAS AFD={(A) / A é um AFD que reconhece Σ*}. Mostre
que a MT L decide TODAS AFD.
L = Sobre a entrada (A), quando A é um AFD.
1. Construa um AFD B que reconhece L(A) como
descrito no exercício 1.10
2. Rode a MT T do teorema 4.4 com a entrada (B),
quando T decide E AFD.
3. Se T aceita, aceite. Se T rejeita, rejeite.
7
4.4. Seja AεGLC = {(G) / G é uma GLC que gera ε}.
Mostre que AεGLC é decidível.
Resposta:
Como AεGLC = {(G) / G é uma GLC que reconhece ε}.
Mostre que a MT V decide AεGLC .
V= Sobre a entrada (G) quando G é uma GLC:
1. Rode a MT S do teorema 4.6 com a entrada (G, ε),
quando S é decidível para AGLC.
2. Se S aceita, aceite. Se S rejeita, rejeite.
8
Problemas
9
4.10 Seja INFINITA AP = {(M)|M é um AP e L(M) é uma
linguagem infinita}. Mostre que INFINITA AP é decidível.
Resposta:
Sabendo uma MT R decide INFINITA AP. Então:
R = “Sobre a entrada (M), onde M é um AP:
1. Seja k o número de estados de M;
2. Construa um AP S que aceite todas as cadeias de
Não gera AP!
comprimento k ou mais;
3. Construa um AP T, tal que L(T) = L(M) ∩ L(S);
Até aqui temos a resolução adequada para ao problema 4.9. Mas, não é útil para este
problema, visto que não há como garantir que a interseção entre dois APs gera um AP.
Então, podemos retomar a resolução deste problema a partir do passo 4 a seguir.
4. Transforme o AP para um GLC;
5. Use o teorema 4.7;
6. Verifique se a GLC é limitada;
7. Se a GLC for limitada, aceite; se não, rejeite.
10
4.12 Seja A = {(R, S)|R e S são expressões regulares e
L (R) ⊆ L (S) }. Mostre que A é decidível.
R é subconjunto de S
S
0*
R
Respostas:
1*
Então L (R) ⊆ L (S), se e apenas se, L(S) ∩ L(R) = Ø.
Faça MT X decide A.
X = “Sobre a entrada (R, S), onde R e S são ER:
1. Construa um AFD E, de tal modo que L(E) = L(S) ∩
L(R);
2. Execute L (E) ≠ Ø, usando o decisor T de E AFD do
teorema 4.4;
3. Se T aceita, aceite. Se T rejeita, rejeite.”
11
4.15 Seja A = {(R) | R é uma expressão regular que
descreve uma linguagem contendo pelo menos uma cadeia
w que tem 111 como uma subcadeia (isto é, w = x111y para
alguma x e alguma y)}. Mostre que A é decidível.
Veja que esta ER não é uma expressão
fixa. Podemos ter: 01110, 10111001
Resposta:
Definindo a MT X que decide A, temos:
X = “ Sobre a entrada (R) onde R é uma ER e w =∑*111∑* :
1. Transforme R e w em: AFN1 e AFN2, respectivamente;
2. Transforme AFN1 e AFN2 em: AFD1 e AFD2,
respectivamente;
3. Para AFD1 definimos M1. Para AFD2 definimos M2. De
modo que L (M1 ∩ M2) = Ø.
4. Execute L (M1 ∩ M2) = Ø, usando o decisor T de Eafd do
teorema 4.4;
5. Se T aceita, rejeite. Se T rejeita, aceite.”
12
Facilitando a compreensão da resolução...
R
∑*111∑*
AFN
AFN
AFD
AFD
M1
M2
L (M1 ∩ M2) = Ø ?
Ver Teorema 4.4.
13
4.19 Seja S = { (M)|M é um AFD que aceita wR sempre
que ele aceita w}. Mostre que S é decidível.
▫ X = a entrada de (M), onde M é um AFD
▫ 1. Construa um AFD N, L(M) R = {wR |w ∈ L(M)}
▫ 2. Execute a MT F do Teorema 4.5
EQAFD = {(A,B)| A e B são AFDs e L(A) = L(B)}
 2.1 – F = “Sobre a entrada (M,N), onde M e N são AFDs”
 2.2 – Construa um AFD C, se L(M) = L(N) então L(C) = Ø
14
4.19 Seja S = { (M)|M é um AFD que aceita wR
sempre que ele aceita w}. Mostre que S é decidível.
 2.3 – Testar a vacuidade de C, Teorema 4.4
VAFD = {(C)| C é um AFD e L(C) = Ø}
 2.3.1 – T = “Sobre a entrada (C), onde C é um AFD”
 2.3.2 – Se nenhum estado de aceitação estiver
marcado, aceite. Caso contrário, rejeite.
 2.4 – Se T aceita, aceite. Se T rejeita, rejeite.
▫ 3. Se F aceita, aceite. Se F rejeita, rejeite.
15
4.24 Seja PALAFD = { (M)|M é um AFD que aceita
algum palíndromo}. Mostre que PALAFD é decidível.
Seja K uma MT que decide EGLC:
D = a entrada de M
1. Construa um AP P, L(P) = {w |w é um palíndromo}
2. Construa um AP P’, tal que, L(P’) = L(P) ∩ L(M)
3.Converta P’ em uma GLC equivalente G
4. K verifica se L(G) está vazia
5. Se L(G) está vazia, rejeite. Se não, aceite.
16
Referências
• Lima, M. A. “Máquinas de Turing: Enumerabilidade e
Decidibilidade”. Faculdade de Ciência da Computação – UFU. 2009.
Disponível
em:
<http://www.facom.ufu.br/~madriana/TC/exercMT.pdf>, acesso
em 04 mai 2013.
• Prado, S. D. “Apostila 06: Teoria da Computação”. Faculdade de
Ciências
–
UNESP.
2009.
Disponível
em:
<http://wwwp.fc.unesp.br/~simonedp/zipados/TC06.pdf>, acesso
em 04 mai 2013.
• Sipser, M. “Introdução à Teoria da Computação”. 2ªed. São Paulo:
Thomson Learning, 2007.
• Vídeo-aula
sobre
Decidibilidade:
<https://class.coursera.org/automata/lecture/27. Esta vídeo-aula
integra o curso de Teoria da Computação do Coursera.
Universidade Federal da Paraíba
Programa de Pós-Graduação em Informática
Teoria da Computação – 2013.1
4 - DECIDIBILIDADE
SIPSER – Exercícios
Equipe: Dorgival Netto, Jarbele Cássia, Silvia Azevedo
{dorgidetto, jarbele.cassia}@gmail.com, [email protected]
(07/05/2013)