153
правки
Изменения
Нет описания правки
Если <tex>MT</tex> остановится, нужно добиться того, чтобы строка закончилась. Иначе строки будут расти до бесконечности, но никогда не закончатся.
<tex>\forall c \in \Pi</tex> построим следующую пару <tex>(a_i=c , b_i = c), (a_i = \$ , b = \$)</tex>.
<tex>b</tex> должно сойтись с соответствующей <tex>a</tex> в предыдущем мгновенном описании.
Соответственно, получаем <tex>a_i = d \#_p</tex>, <tex>b_i = \#_q c</tex> и <tex>\delta(q, c) = \langle p, d, \rightarrow \rangle</tex>, а также <tex>a_i = \#_p a d</tex>, <tex>b_i a \#_q e</tex> и <tex>\delta (a, c) = \langle p, d, \leftarrow \rangle </tex>.Аналогично поступаем следует поступить и с переходом на месте, или считаем, что такого не бывает.
Как может быть устроен префикс решения '''МПСП''':
<tex>b</tex>: <tex>| \$ | \omega_1 | \omega_2 \ldots | \$ | \#_y \$ \$ |</tex>
Требуется добиться остановки. Для этого добавляется далее:
* <tex>b_{n+1} = *\$</tex>
Возникающее однозначное соответствие может быть решением этой системы и решением исходной задачи, к в которой всё начиналось с пары <tex>(a_1, b_1)</tex>.
}}
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
