Изменения

&nbsp;&nbsp;&nbsp;&nbsp;Рассмотрим слово w, которое принимает автомат НКА: <tex>\langle s, w_1w_2...w_m \rangle \vdash \langle u_1, w_2...w_m \rangle \vdash \langle u_m, \varepsilon \rangle</tex>, и <tex>u_m \in T</tex>

&nbsp;&nbsp;&nbsp;&nbsp;Проверим, что построенный ДКА тоже принимает это слово.

&nbsp;&nbsp;&nbsp;&nbsp;Заметим, что <tex>s \in s_d</tex>, а, значит, исходя из нашего наблюдения мы получаем, что <tex>u_1 \in {u_d}_1</tex>, где <tex>{u_d}_1 = \delta_d(s, w_1)</tex>.

&nbsp;&nbsp;&nbsp;&nbsp;Далее несложно заметить, что <tex>\forall i \leq m : u_i \in {u_d}_i</tex>, где <tex>\langle s_d, w_1w_2...w_m \rangle \vdash \langle {u_d}_1, w_2...w_m \rangle \vdash \langle {u_d}_i, w_{i + 1}...w_m \rangle</tex>.

&nbsp;&nbsp;&nbsp;&nbsp;Таким образом, <tex>u_m \in {u_d}_m</tex>, а из определения терминальных состояний в построенном ДКА мы получаем, что <tex>{u_d}_m \in T_d</tex>, а, значит, наш ДКА, тоже принимает cлово w. &nbsp;&nbsp;&nbsp;&nbsp;Рассмотрим последовательность состояний НКА, когда принимали слово - <tex>(q_1, ..., q_m)</tex> - и последовательность состояний ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</tex>. &nbsp;&nbsp;&nbsp;&nbsp;Мы знаем, что <tex>q_m</tex> - терминальная, так как НКА принимает слово. Надо доказать, что <tex>{q_d}_m</tex> - терминальная. &nbsp;&nbsp;&nbsp;&nbsp;Заметим, что <tex>q_1 \in {q_d}_1</tex> - так как это стартовые состояния, а, значит, по нашему наблюдению <tex>q_2 \in {q_d}_2</tex> и так далее. Получается, что <tex>q_m \in {q_d}_m</tex>. Мы знаем, что <tex>q_m</tex> - терминальная вершина, а, значит, по определению терминальной вершины в нашем ДКА, что <tex>{q_d}_m</tex> - тоже терминальная.