Problema da Correspondência de Post

Prévia do material em texto

PUC GOIÁS
ESCOLA DE CIÊNCIAS EXATAS E DA
COMPUTAÇÃO
CMP1067 Projeto e Análise de Algoritmos II
Marco A. F. Menezes
AULA 9
Referências: esta aula está baseada no seguinte livro,
1. Michael Sipser. Introdução à Teoria da Computação. Tradução: Ruy
José Guerra Barretto de Queiroz. São Paulo: Thomson Learning, 2007.
Aula anterior
3.2 O problema da correspondência de Post
Definição 3.3 O problema da correspondência de Post, denotado por
PCP , é determinar se uma coleção de dominós
P = {[
t1
b1
], [
t2
b2
], . . . , [
tk
bk
]},
cujos termos em ti, bi, i = 1, 2, . . . , k, pertencem a um alfabeto Σ, |Σ| > 1,
tem um emparelhamento (i1, i2, . . . , il), em que
ti1 , ti2 , . . . , til = bi1 , bi2 , . . . , bil .
Ou seja, em termos de linguagem,
PCP = {< P >; P e uma instancia do PCP com um emparelhamento}.
1
Exemplo Seja dada uma coleção de dominós
P = {[
b
ca
], [
a
ab
], [
ca
a
], [
abc
c
]}
e outra
Q = {[
abc
ab
], [
ca
a
], [
acc
ba
]}.
Encontre emparelhamentos, se posśıvel.
Resolução
Definição 3.4 O problema da correspondência de Post modificado, de-
notado por PCPM , é determinar se uma coleção de dominós P tem um
emparelhamento que começa com o primeiro dominó. Ou seja, em termos de
linguagem,
PCPM = {< P >; P e uma instancia do PCP com um emparelhamento
que comeca com o primeiro domino}.
Exemplo Considere a instância P do exemplo anterior. Encontre um
emparelhamento para o PCPM, se posśıvel. Senão, mude P para um empa-
relhamento ser posśıvel.
Resolução
Lema ≤m é uma relação transitiva.
Demonstração
Teorema 3.4 PCP é indecid́ıvel.
Demonstração
Exerćıcios para casa Fazer a Lista 3.
Próxima aula Unidade 3 - Redutibilidade: Lista 3.
2