Изменения

Пусть <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex> {{---}} ДКА, допускающий язык <tex>L</tex>. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex>, которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta(q_i, y) \in F</tex>.<br>Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q_j q \in Q \mid \delta(q_j, q_k) exists a \in Q\Sigma, q_k q' \in S_n , \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</tex>.<br>Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>.<br>Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.