Обсуждение участницы:Анна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
 
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
 
|proof =
 
|proof =
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА и порождающее его регулярное выражение. Оба эти факта могут быть использованы для доказательства утверждения. Мы выберем первый.<br>
+
Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </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>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 \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять <tex>S_n</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 \in Q \mid \exists a \in \Sigma, 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>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>
Строка 23: Строка 22:
 
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
 
Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.
 
|proof =
 
|proof =
 
+
Так как <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>.
 
}}
 
}}

Версия 22:32, 12 декабря 2016

Определение:
Определим [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]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]. Следовательно, данный язык является регулярным.
[math]\triangleleft[/math]
Утверждение:
Пусть [math]L[/math] — регулярный язык. Тогда язык [math]cycle(L)[/math] также регулярен.
[math]\triangleright[/math]
Так как [math]L[/math] — регулярный язык, то существует допускающий его ДКА [math]M = \langle \Sigma , Q , q_0 , F , \delta \rangle [/math].
[math]\triangleleft[/math]