Изменения
→Доказательство эквивалентности
<tex>1.</tex> Докажем, что любое слово, которое принимает НКА, будет принято построенным ДКА.
Сделаем Сначала сделаем наблюдение, что если <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_n, \varepsilon \rangle</tex>. Проверим, что построенный ДКА тоже принимает это слово.
Рассмотрим последовательность состояний НКА, когда принимали слово - <tex>(q_1, ..., q_m)</tex> - и последовательность состояний ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</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>.
Рассмотрим последовательность состояний ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</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> по нужной строке, а, значит, что НКА принимает это слово.
