Изменения
Отмена правки 11726 участника 192.168.0.2 (обсуждение)
Проверим, что построенный ДКА тоже принимает это слово.
Заметим, что <tex>s \in s_d</tex>, а, значит, исходя из нашего наблюдения мы получаем, что <tex>u_1 \in {u_d}_1</tex>, где <tex>{u_d}_1 = \delta_d(s, w_1)</tex>.
Далее несложно заметить, что <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>.
Таким образом, <tex>u_m \in {u_d}_m</tex>, а из определения терминальных состояний в построенном ДКА мы получаем, что <tex>{u_d}_m \in T_d</tex>, а, значит, наш ДКА, тоже принимает cлово w.
Рассмотрим последовательность состояний НКА, когда принимали слово - <tex>(q_1, ..., q_m)</tex> - и последовательность состояний ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</tex>.
Мы знаем, что <tex>q_m</tex> - терминальная, так как НКА принимает слово. Надо доказать, что <tex>{q_d}_m</tex> - терминальная.
Заметим, что <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> - тоже терминальная.
<tex>2.</tex> Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА.
