153
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Постовской системой соответствия над алфавитом <tex>\Sigma</tex> ''' называется упорядоченная пара конечных последовательностей <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>, где <tex>x_i \in \Sigma ^*</tex> и <tex>x_i \in \Sigma ^*</tex> для всех '''i'''.
}}
{{Определение
|definition=
'''Решением постовской системы соответствия <tex>(( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ))</tex>''' называется непустая последовательность индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющая условию <tex>
x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j.
}}
===Пример===
Пусть <tex>\Sigma = \{ a , b , c \}</tex>. Рассмотрим постовскую систему соответствия <tex>((aab, a, caa),(a, aa, bc))</tex>.
Последовательность <tex>(2,1,3,2,2)</tex> является решением этой системы, так как <tex>a \cdot aab \cdot caa \cdot a \cdot a =
aa \cdot a \cdot bc \cdot aa \cdot aa</tex>.
{{Определение
|definition=
'''Проблемой соответствий Поста''' (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.
}}
{{Теорема
|statement=
Пусть <tex>| \Sigma | \geq 2</tex>. Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом <tex>\Sigma</tex> узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)
|proof=
}}
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
