Изменения

Смысл алгоритма состоит в замене множества Данный алгоритм заменяет НКА из <tex>n</tex> состояний НКА, множеством на эквивалентный ДКА из <tex>2^n</tex> подмножеств его состояний.

Генерируем все подмножества множества '''Задание состояний:''' Состояние нашего ДКА будет соответствовать подмножеству состояний НКА - то есть их будет ровно <tex>2^n</tex>. '''Задание переходов:''' Возьмём состояние нашего ДКА <tex>q</tex>, соответствующее подмножеству состояний НКА {{---}} это состояния <tex>(a_1, a_2, ..., a_m)</tex>, и символ <tex>c</tex>. Тогда <tex>\delta_D(q, c) = p</tex>, где p - состояние ДКА.Далее для всевозможных , соответствующее подмножеству состояний НКА - <tex>\cup_{i=1}^{m} \delta(q_1a_i, q_2c)</tex>, где <tex>\delta_D</tex> {{---}} пар состояний функция перехода в ДКА и символов , а <tex>c\delta</tex> {{---}} добавляем переход функция перехода в НКА. '''Задание стартового состояния:''' Стартовое состояние - состояние ДКА, соответствующее множеству из одного стартового состояния НКА. '''Задание терминальных вершин:''' Если в подмножестве состояний НКА есть хотя бы одна терминальная вершина, то вершина ДКА, соответствующая этому подмножеству, будет терминальной. '''Терминология:''' <tex>q</tex> - состояние НКА. <tex>q_d</tex> - состояние ДКА. <tex>\delta</tex> - функция перехода в НКА. <tex>q_1\delta_D</tex> - функция перехода в ДКА. <tex>q \in q_d</tex> - <tex>q</tex> принадлежит <tex>q_d</tex>, если множество состояний НКА, соответствующее состоянию <tex>q_d</tex>, содержит состояние <tex>q</tex>. ===Доказательство эквивалентности==={{Теорема|statement=Построенный ДКА эквивалентен данному НКА.|proof=&nbsp;<tex>1.</tex> Докажем, что любое слово, которое принимает НКА, будет принято построенным ДКА. Сделаем наблюдение, что если <tex>q \in q_d</tex>q_2и символ перехода - <tex>c</tex> по , то <tex>\forall p \in \delta(q, c)</tex>: <tex>p \in \delta_D(q_d, если для каждого состояния c)</tex>. Рассмотрим последовательность состояний НКА из , когда принимали слово - <tex>(q_1, ..., q_m)</tex> есть переход по - и последовательность состояний ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</tex>. Мы знаем, что <tex>q_m</tex> - терминальная, так как НКА принимает слово. Надо доказать, что <tex>{q_d}_m</tex> - терминальная. Заметим, что <tex>cq_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> Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА. Рассмотрим последовательность состояний НКА из , когда принимали слово - <tex>(q_1, ..., q_m)</tex> - и последовательность состояний ДКА, когда принимали слово - <tex>q_2({q_d}_1, ..., {q_d}_m)</tex> есть переход из состояния из . Мы знаем, что <tex>q_1{q_d}_m</tex> по - терминальная, так как ДКА принимает слово. Надо доказать, что <tex>cq_m</tex>- терминальная.  }}