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