|
Так как [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} = \{ q_j \mid \delta(q_j, q_k) \in Q, q_k \in S_n \}[/math] — множество состояний, из которых есть переход в какое-либо состояние из [math]S_n[/math] (по единственному символу). |
