| Определение: |
| Определим [math]half(L)[/math] как множество первых половин цепочек языка [math]L[/math], то есть множество [math]\{ w \mid [/math] существует [math]x[/math], для которой [math]wx \in L[/math], причем [math]|w| = |x| \}[/math]. |
Например, если [math]L = \{ \varepsilon, 0010, 011, 010110 \}[/math], то [math]half(L) = \{ \varepsilon, 00, 010 \}[/math]. Заметим, что цепочки нечетной длины не влияют на [math]half(L)[/math].
| Определение: |
| Определим [math]cycle(L)[/math] как множество [math]\{ w \mid [/math] цепочку [math]w[/math] можно представить в виде [math]w = xy[/math], где [math]yx \in L \}[/math]. |
Например, если [math]L = \{ 01, 011 \}[/math], то [math]cycle(L) = \{ 01, 10, 011, 110, 101 \}[/math].
| Утверждение: |
Пусть [math]L[/math] — регулярный язык. Тогда язык [math]half(L)[/math] также регулярен. |
| [math]\triangleright[/math] |
|
Так как [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] (по единственному символу). |
| [math]\triangleleft[/math] |
| Утверждение: |
Пусть [math]L[/math] — регулярный язык. Тогда язык [math]cycle(L)[/math] также регулярен. |
