Decidibilidade
continuação…
1
Teorema:
Para qualquer linguagem recursivamente
enumerável L é indecidível determinar se
L é finita
Prova:
Vamos reduzir o problema da parada
a este problema
2
Seja M uma máquina que aceita L
L(M )  L
Suponha que temos um algoritmo para
determinar se a linguagem de M é finita:
SIM L ( M ) finita
M
Algoritmo para
o problema de
linguagem finita NÃO L ( M ) infinita
3
Vamos contruir um algoritmo para
resolver o problema da parada:
M
w
Algoritm para
o problema da
parada
SIM
M pára sobre w
NÃO
não
w
M
pára sobre
4
Primeiro construa a máquina M w :
Inicialmente, simule M sobre a entrada w
Se M entra em um estado de parada,
aceite qualquer entrada (linguagem inifinita)
Caso contrário não aceite nada (linguagem finita)
5
M pára sobre w
se e
somente se
L ( M w ) é infinita
6
Algoritmo para o problema da parada:
Entrada: máquina M e string w
1. Construa
Mw
2. Determine se L ( M w ) é finita
SIM: então M não pára sobre w
NÃO: então M pára sobre w
7
Máquina para o problema da parada
M
construa
w
Mw
Verifique se
L(M w )
é finita
SIM
NÃO
NÃO
SIM
8
Teorema:
Para qualquer linguagem recursivamente
enumerável L
é indecidível determinar se L contém
dois strings distintos de mesmo comprimento
Prova: Vamos reduzir o problema da parada
a este problema
9
Seja M uma máquina que aceita L
L(M )  L
Suponha que temos um algotimo para
o problema dos dois strings:
M
Algoritmo para
o problema dos
dois strings
SIM L ( M ) contém
NÃO L ( M ) não
contém
dois strings de mesmo comprimento
10
Vamos construir um algoritmo
para o problema da parada:
M
w
Algoritm para
o problema
da parada
SIM
M pára sobre w
NÃO
não
w
M
pára sobre
11
Primeiro construa a máquina M w :
Inicialmente, simule M sobre a entrada w
Se M entra em um estado de parada,
aceite os símbolos a e b
(dois strings de mesmo comprimento)
12
M
pára sobre w
se e
somente se
M w aceita a e b
(dois strings de mesmo comprimento)
13
Algoritmo para o problema da parada:
Entrada: máquina M e string w
1. Construa
Mw
2. Determine se M w aceita
dois strings de mesmo comprimento
SIM: então M pára sobre w
NÃO: então M não pára sobre w
14
Maáquina para o problema da parada
M
construa
w
Mw
Verifique se
L(M w )
tem dois
strings
de mesmo
comprimento
SIM
SIM
NÃO
NÃO
15
O Problema de
Correspondência de Post
16
Alguns probelmas indecidíveis sobre
linguagens livres de contexto:
• Uma gramática livre de contexto G
é ambígua ?
• Para gramáticas livres de contexto G1, G2
L ( G1 )  L ( G 2 )  
17
Vamos precisar de uma ferramenta para
provar que esses dois problemas sobre
linguagens livres de contexto são
indecidíveis:
O Problema de Correspondência de Post
18
O Problema de Correspondência de Post
Entrada: Duas sequências de strings
A  w1 , w 2 ,  , w n
B  v1 , v 2 ,  , v n
19
Existe solução para a Correspondência de Post
se existe uma sequência i , j ,  , k tal que:
wi w j  w k  vi v j  v k
solução-PC
20
Exemplo:
A:
B:
solução-PC: 2 ,1,3
w1
w2
100
11
w3
111
v1
v2
v3
001
111
11
w 2 w1 w3  v 2 v1v 3
11100111
21
Exemplo:
A:
B:
w1
w2
00
001
w3
1000
v1
v2
v3
0
11
011
Não tem solução
Porque o comprimento total dos strings de B
é menor que o comprimento total dos de A
22
Problema Correspondência de Post Modificado
Entradas: A  w1 , w 2 ,  , w n
B  v1 , v 2 ,  , v n
solução-MPC:
1, i , j ,  , k
w1 w i w j  w k  v1v i v j  v k
23
Exemplo:
A:
B:
solução-MPC:
1,3 , 2
w2
w1
11
111
w3
100
v1
v2
v3
111
11
001
w1 w3 w 2  v1v 2 v 3
11100111
24
1. Vamos provar que o problema
MPC é indecidível
2. Vamos provar que o problema
PC é indecidível
25
1. Vamos provar que o problema
MPC é indecidível
Vamos reduzir o problema de pertinência
ao problema MPC
26
Problema de pertinência:
Entrada: linguagem recursivamente
enumerável L
string w
Questão: w  L ?
Indecidível
27
Problema de pertinência:
Entrada: gramática irrestrita G
string w
Questão:
w  L (G ) ?
Indecidível
28
Redução do problema de pertinência
ao problema MPC:
Para uma gramática irrestrita G e string w
construímos um par
A, B
A, B
tal que
tem uma solução-MPC
se e somente se w  L (G )
29
A
FS 
B
F
Gramática G
S : variável inicial
F : símbolo especial
a
a
Para todo terminal a
V
V
Para toda variável V
30
A
E
B
 wE
Gramática G
string w
E : símbolo especial
y
x
Para toda produção
x y


31
Exemplo:
Gramática G
:
S  aABb | Bbb
Bb  C
AC  aac
String
w  aaac
32
A
B
w1 :
FS 
v1 :
F
w2 :
a
v2 :
a

w8 :
b
b
c
c
A
A

B
B
C
C
S
v8 :
S
33
A
w9 :

B
E
v9 :
aABb
S
Bbb
S
C

aac
w14 :
aaacE

Bb
AC
v14 :

34
Gramática G
:
S  aABb | Bbb
Bb  C
AC  aac
aaac  L (G )
S  aABb  aAC  aaac
35
S  aABb
A
w1
w10
F S  a A B b
v1 v10
B
36
S  aABb  aAC
A
w1
w10
w14 w 2 w 5 w12
F S  a A B b a A C
v1 v10 v14 v 2 v 5 v12
B
37
S  aABb  aAC  aaac
A
w1
w10
w14 w 2 w 5 w12 w w 2 w13
14
w9
F S  a A B b a A C
 a a a c E
v1 v10 v14 v 2 v v12 v14 v 2 v13
5
v9
B
38
Teorema:
( A , B ) tem uma solução-MPC
se e somente se w  L (G )
39
Algoritmo para o problema de pertinência:
Entrada: gramática irrestrita G
string w
Construa o par
A, B
se A, B tem uma solução-MPC então w  L (G )
senão w  L (G )
40
Máquina para o Problema de Pertinência
solução
G
w
construa
A, B
A, B algoritmo
MPC
w  L (G )
w  L (G )
sem-solução
41
2. Vamos provar que o problema
PC é indecidível
Vamos reduzir o problema MPC
ao problema PC
42
A, B
: entrada para o problema MPC
A  w1 , w 2 ,  , w n
B  v1 , v 2 ,  , v n
43
Construímos novas sequências C , D
C  w 0 , w1 ,  , w n , w n  1
D  v 0 , v1 ,  , v n , v n  1
A  w1 , w 2 ,  , w n
B  v1 , v 2 ,  , v n
44
A
C
wi  abcad
wi  a * b * c * a * d *
Inserimos um símbolo especial entre
quaisquer dois símbolos
45
B
v i  abcad
D
v i  * a * b * c * a * d
46
Casos Especiais
C
D
w 0  * w1
v 0  v1
w n 1  
v n  1  * 
47
Observação:
Existe uma solução-PC para C , D
se e
somente
se
existe uma solução-MPC para A, B
48
solução-PC
w 0  w k w n  1  v 0  w k v n  1
solução-MPC
w1  w k  v1  v k
49
Algoritmo MPC:
Entrada: sequências
A, B
Construa sequências C , D
Resolva o problema PC para C , D
50
Algoritmo MPC
A, B
construa
C,D
C , D algoritmo
solução
PC
sem-solução
51