Изменения

&nbsp;<tex>1.</tex> Докажем, что любое слово, которое принимает НКА, будет принято построенным ДКА.

&nbsp;&nbsp;&nbsp;&nbsp;Сделаем наблюдение, что если <tex>q \in q_d</tex> и символ перехода - <tex>c</tex>, то <tex>\forall p \in \delta(q, c)</tex>: <tex>p \in \delta_D(q_d, c)</tex>.

&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> - тоже терминальная.

&nbsp;<tex>2.</tex> Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА.

&nbsp;&nbsp;&nbsp;&nbsp;Рассмотрим последовательность состояний НКА, когда принимали слово - <tex>(q_1, ..., q_m)</tex> - и последовательность состояний ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</tex>.

Мы знаем&nbsp;&nbsp;&nbsp;&nbsp;Сделаем наблюдение, что если <tex>{q_d}_m</tex> , соответствует множеству из одного элемента - терминальная<tex>q</tex>, так как ДКА принимает слово. Надо доказатьи мы из него достигли по строке <tex>S</tex> какого-то состояния <tex>p_d</tex>, что то <tex>\forall p \in p_d</tex>: существует путь из <tex>q</tex> в <tex>p</tex> в НКА по строке <tex>q_mS</tex> - терминальная.