Problème de courrier postal

Le problème de la correspondance postale (PCP), introduit par Emil Post en 1946, est un problème de décision indécidable. Le problème PCP sur un alphabet ∑ est énoncé comme suit -

Compte tenu des deux listes suivantes, M et N de chaînes non vides sur ∑ -

M = (x ₁ , x ₂ , x ₃ , ………, x _n )

N = (y ₁ , y ₂ , y ₃ , ………, y _n )

On peut dire qu'il existe une solution de post-correspondance, si pour certains i ₁ , i ₂ , ………… i _k , où 1 ≤ i _j ≤ n, la condition x _i1 …… .x _ik = y _i1 ……. y _ik satisfait.

Exemple 1

Vérifiez si les listes

M = (abb, aa, aaa) et N = (bba, aaa, aa)

avez une solution de courrier postal?

Solution

	x 1	x 2	x 3
M	Abb	aa	aaa
N	Bba	aaa	aa

Ici,

x₂x₁x₃ = ‘aaabbaaa’

et y₂y₁y₃ = ‘aaabbaaa’

On peut voir ça

x₂x₁x₃ = y₂y₁y₃

Par conséquent, la solution est i = 2, j = 1, and k = 3.

Exemple 2

Vérifiez si les listes M = (ab, bab, bbaaa) et N = (a, ba, bab) avez une solution de courrier postal?

Solution

	x 1	x 2	x 3
M	un B	bab	bbaaa
N	une	ba	bab

Dans ce cas, il n'y a pas de solution car -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Les longueurs ne sont pas les mêmes)

Par conséquent, on peut dire que ce problème de correspondance postérieure est undecidable.