153
правки
Изменения
Нет описания правки
Получаем <tex>\$ A_0 \$ \ldots \$ A_k \$</tex>, <tex>\$ A_i \ldots</tex>.
Если <tex>MT</tex> остановится, добъёмся добьёмся того, что зак. Иначе строки будут расти до бесконечности, но никогда не закончатся.
<tex>\forall c \in \Pi</tex> заведём пару <tex>(a_i=c b_i = c), (a_i = \$ b = \$)</tex>.
Аналогично поступаем и с переходом на месте, или считаем, что такого не бывает.
Как может быть устроен префикс решения '''МПСП''':
<tex>| \$ | \#_s \omega_1 \$ | d \#_p | w_2 \ldots | \$ | \#_y \$ | \$ |</tex>
<tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex>
т.е. добавляем элементы и находим соответствующие переходы.
Добавим далее:
* <tex>a = \#_y, b = \#_y c</tex>
* или <tex>a = \#_y, b = c \#_y</tex>
* или <tex>a = \$, b = \#_y \$ \$</tex>
}}
Теперь остаётся избавиться от требования фиксированного первого индекса, т.е. перейти от '''МПСП''' к '''ПСП''': '''ВерноИзвестно''':* умеем Существует решение '''1ПСПМПСП''' <tex>\Rightarrow</tex> умеем существует решение '''ПСП'''* не умеем Не существует решения '''1ПСПМПСП''' <tex>\Leftarrow</tex>не умеем существует решения '''ПСП'''
'''Необходимо''':
* не умеем Не существует решения '''1ПСПМПСП''' <tex>\Rightarrow</tex> не умеем существует решения '''ПСП'''
Возьмём экземпляр задачи 1ПСПМПСП: <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>. Вставим между каждой парой символов во всех строках символ <tex>*</tex>.
<tex>i = 1</tex>
* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex>
* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex>
<tex>i = 2 \ldots n </tex>:
* <tex>a_i = c_1 c_2 \ldots c_l \rightarrow a_i = c_1 * c_2 * \ldots * c_l *</tex>
* <tex>b_i = c_1 c_2 \ldots c_l \rightarrow b_i = c_1 * c_2 * \ldots * c_l</tex>
<tex>i = n + 1</tex>* <tex>a_1 = * c_1 * c_2 \ldots c_l *</tex>* <tex>b_1 = * c_1 * c_2 \ldots c_l</tex>Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.
* <tex>a_{n+1} = \$</tex>
* <tex>b_{n+1} = *\$</tex>
Нужно начать с <tex>(a_1, b_1)</tex>, т.к. все остальные пары начинаются с различных символов.
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к которой всё начиналось с пары <tex>(a_1, b_1)</tex>.
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
