29
правок
Изменения
м
leq/geq
{{Определение
|definition=
Даны два конечных списка <tex>A = (a_1, \ldots, a_n)</tex> и <tex>B = (b_1 ,\ldots ,b_n)</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>(i_1 , \ldots, i_k)</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex>1 \leq leqslant i_j \leq leqslant n</tex> для всех j, называется '''проблемой соответствий Поста (ПСП)'''. Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.
}}
Для списков <tex>A</tex> и <tex>B</tex> размера <tex>n</tex> из условия ПСП построим программу-полуразрешитель <tex>p</tex>, проверяющую все возможные решения:
for <tex>m = 1 .. \infty</tex>
for all <tex>(i_1, i_2, \ldots, i_m): 1 \leq leqslant i_j \leq leqslant n</tex>
if <tex>a_{i_1} \ldots a_{i_m} = b_{i_1} \ldots b_{i_m}</tex>
return true
