Problema de Correspondência
de Post (PCP)
Teoria da Computação
O problema PCP
Input
g
abc
bcd
bcd
fg
eg
b
ef
1
2
3
4
…
ef
cde
n
Pergunta : É possivel encontrar uma sequência de
peças tal que o string formado na parte de cima e
idêntico ao string formado na parte de baixo ?
bcdefg
bcdefg
Sequência : 3 n 1
Exemplos
b
a
ca
abc
ca
ab
a
c
1
2
3
4
abcaaabc
abcaaabc
Sequência de peças= 2 1 3 2 4
Exemplo
Input
abc
ca
acc
ab
a
ba
1
2
3
Resposta ??
Não
Justificativa : a parte de cima das peças é sempre
maior que a parte de baixo !
Formalização do Problema
Input genérico do Problema PCP
C={
t1
b1
,
t2
b2
,
t3
b3
, …
,
tn
bn
}
t1, t2, …, tn são strings sobre um alfabeto S
b1, b2, …, bn são strings sobre um alfabeto S
Um pareamento (match) = uma sequência <i1, i2, …, ik> de
números em {1,…,n}
tal que
ti1 ti2 … tik = bi1 bi2 … bik
= string do pareamento
Formalização do Problema
• Pergunta do problema PCP :
Existe um pareamento para o input C ?
Configurações de uma MT
M = Máquina de Turing
w = string (por exemplo w = (0002102)
0
0
0
2
1
q
q0 0 0 0 2 1 0 2
0
2
B
B
B
0002q102
Configuração Inicial = Cin
0 0 0 2 qa 1 0 2
Configuração de Aceitação = Ca
0 0 0 2 qr 1 0 2
Configuração de Rejeição = Cr
B
Um passo de cálculo
Configuração 1  Configuração 2
0
0
0
2
1
4
0
2
B
B
q
0002q102
000q2402
B
B
Um passo de cálculo
Configuração 1  Configuração 2
0
0
0
2
1
4
0
2
B
q
0002q102
0 0 0 2 4 q0 2
B
B
B
Histórico de configurações
• M : máquina de Turing
• w = string sobre o alfabeto de M
• Histórico de configurações de M em w
Cin # C1 # C2 # …. # Ca
Cin # C1 # C2 # …. # Cr
Cin # C1 # C2 # …. # Cn …..
Problema PCP é indecidível
Técnica = redução de ATM para PCP
ATM
<M,w>
PCP
Um conjunto de peças, onde os
strings correspondem aos possiveis
passos de M ao ser executada em w
String pareado = corresponderá ao histórico de aceitação de w por M
Pareamento = corresponderá aos passos executados pela máquina,
partindo da configuração inicial até chegar numa configuração de
aceitação.
Assim : M aceita w se e somente se existir este pareamento
Idéia de Emil Post
#
Cin # C2 #
Cn #
#Cin
C2 #
Ca #
C3 #
Ca #
Primeira peça
String pareado = # Cin # C2 # C3 … # Ca #
Pareamento = sequência de peças correspondendo aos passos
realizados pela máquina até chegar no estado de aceitação qa
Peças = correspondem aos passos (transições) da
máquina de Turing
Exemplo
•
•
•
•
•
•
•
•
d(qo,0) = (q1,2,R)
d(q1,1) = (q2,0,R)
d(q2,0) = (q3,2,L)
d(q2,1) = (qr,1,R)
d(q3,0) = (q3,0,R)
d(q3,2) = (q3,2,R)
d(q3,2) = (q3,2,R)
d(q3,B) = (qa,B,R)
Máquina de Turing M
• w=0100
q0 0 1 0 0
2 0 q3 2 0
2 q1 1 0 0
2 0 2 q3 0
2 0 q2
2 0 2 0 q3
00
2 q3 0 2 0
2 0 2 0 B qa
Idéia
#
Cin # C2 #
C3 #
# Cin #
C2 #
C4 #
C3 #
Primeira peça
#
#q
0
0100
#
#
#q
0
0100
#
q0 0 1 0 0 #
2 q1 1 0 0 #
2 0 q2 0 0 #
2 q1 1 0 0 #
2 0 q2 0 0 #
2 q3 0 2 0 #
PEÇAS
g0 0
q
q1 1
0b qc2d0
1
2
0
#
2f gq1
0 q2
bq3 0 2
1
2
0
#
Problema
Definir um conjunto fixo de peças tal que seja possivel encadear
algumas dessas peças (no caso de M aceitar w) de modo a construir o string
de pareamento (em baixo e em cima da sequência das peças) :
# q0 0 1 0 0 # 2 q1 1 0 0 # 2 0 q2 0 0 # 2 q3 0 2 0 # 2 0 q3 2 0 #
2 0 2 q3 0 # 2 0 2 0 q3 # 2 0 2 0 B qa #
A DESCRIÇÃO DAS PEÇAS FAZ USO DO CÓDIGO DA MÁQUINA E O STRING w