Problema de correspondencia posterior
El problema posterior a la correspondencia (PCP), presentado por Emil Post en 1946, es un problema de decisión indecidible. El problema de PCP sobre un alfabeto ∑ se expresa de la siguiente manera:
Dadas las dos listas siguientes, M y N de cadenas no vacías sobre ∑ -
M = (x 1 , x 2 , x 3 , ………, x n )
N = (y 1 , y 2 , y 3 , ………, y n )
Podemos decir que existe una Solución Post Correspondencia, si para algunos i 1 , i 2 , ………… i k , donde 1 ≤ i j ≤ n, la condición x i1 …… .x ik = y i1 ……. y ik satisface.
Ejemplo 1
Encuentre si las listas
M = (abb, aa, aaa) y N = (bba, aaa, aa)
¿Tiene una solución posterior a la correspondencia?
Solución
| x 1 | x 2 | x 3 | |
|---|---|---|---|
| METRO | Tejido | Automóvil club británico | aaa |
| norte | Bba | aaa | Automóvil club británico |
Aquí,
x2x1x3 = ‘aaabbaaa’
y y2y1y3 = ‘aaabbaaa’
Podemos ver eso
x2x1x3 = y2y1y3
Por tanto, la solución es i = 2, j = 1, and k = 3.
Ejemplo 2
Encuentre si las listas M = (ab, bab, bbaaa) y N = (a, ba, bab) ¿Tiene una solución posterior a la correspondencia?
Solución
| x 1 | x 2 | x 3 | |
|---|---|---|---|
| METRO | ab | bab | bbaaa |
| norte | una | licenciado en Letras | bab |
En este caso, no hay solución porque -
| x2x1x3 | ≠ | y2y1y3 | (Las longitudes no son las mismas)
Por lo tanto, se puede decir que este problema de correspondencia posterior es undecidable.