Изменения
→Доказательство эквивалентности
Сначала сделаем наблюдение, что если <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>.
Рассмотрим слово 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>.
Проверим, что построенный ДКА тоже принимает это слово.
Далее несложно заметить, что <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лово <tex>w</tex>.
<tex>2.</tex> Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА.
Сначала сделаем наблюдение, что если <tex>q_d</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>S</tex>.
Рассмотрим последовательность состояний слово w, которое принимает автомат ДКА, когда принимали слово - : <tex>(\langle s_d, w_1w_2...w_m \rangle \vdash \langle {q_du_d}_1, w_2...w_m \rangle \vdash \langle {u_d}_m, \varepsilon \rangle</tex>, и <tex>{q_du_d}_m)\in T_d</tex>.
А так как <tex>{q_d}_1</tex> - стартовое состояние, соответствует множеству из одного элемента - <tex>q_1</tex> - стартовое состояние. Мы из <tex>{q_d}_1</tex> достигли <tex>{q_d}_m</tex>, возьмём любое терминальное состояние <tex>q_m \in {q_d}_m</tex> - по нашему наблюдению, в НКА есть путь из <tex>q_1</tex> в <tex>q_m</tex> по нужной строке, а, значитПроверим, что НКА тоже принимает это слово.
Получается, что мы доказали, что если НКА принимает слово, равносильно тому, что ДКА его тоже принимает. А это означает, что автоматы эквивалентны.
}}
