Изменения

Рассмотрим конечный алфавит <mathtex> \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} </mathtex>. <br>Рассмотрим множество строк над алфавитом <mathtex> \Sigma \cup \Sigma^{-1} ; \; S = S_1 S_2 s_1 s_2 \dots S_k s_k , \; символ a s_i \in \Sigma \cup \Sigma^{-1} </mathtex>. <br>

<mathtex>S</mathtex> и <mathtex>S'</mathtex> называются '''эквивалентными''', если они могут быть превращены друг в друга вставками и удалениями из произвольных мест <mathtex>aa^{-1}</mathtex> и <mathtex>a^{-1}a</mathtex>.

Таким образом, <mathtex> \Sigma \cup \Sigma^{-1} </mathtex> с операцией конкатенации будет [[группа|группой ]] (обратным элементом будет обращение строки с заменой всех символов на «обратные» им).

<mathtex> \Sigma \cup \Sigma^{-1} </mathtex> называется '''свободной группой, порожденной алфавитом <mathtex>\Sigma</mathtex>'''.

Рассмотрим строку. Проредуцируем её (будем последовательно удалять <mathtex>aa^{-1}</mathtex> из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: ''правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?''

У одной строки существует лишь одна редуцированная строка.

Пусть существуют 2 проредуцированные строки <mathtex>\omega_1</mathtex> и <mathtex>\omega_2</mathtex>, заданные одной строкой. Тогда существуют цепочки вставок и удалений <br><mathtex>\omega_1 \rightarrow S_1 \rightarrow S_2 \dots \rightarrow S_k \rightarrow \omega_2 </mathtex>, где <mathtex>\rightarrow</mathtex> − операция вставки или удаления <mathtex>aa^{-1}</mathtex>. (Существование цепочки обеспечено тем, что эти строки образованы одним элементом). <br>

Среди цепочек рассмотрим такую, у которой минимально <mathtex>\sum |S_i|</mathtex> и пусть <mathtex>S_i</mathtex> − строка наибольшей длины. <br>Рассмотрим <mathtex> S_{i - 1} \rightarrow S_i \rightarrow S_{i + 1} </mathtex>, причем мы знаем, что переходы от <mathtex>i</mathtex> к <mathtex>i - 1</mathtex> и <mathtex>i + 1</mathtex> обеспечены за счет удаления (из-за того, что длина <mathtex>S_i</mathtex> максимальна). Эти переходы могут быть обеспечены за счет:# Двух непересекающихся пар. Тогда пусть <mathtex> S_{i - 1} = L_1 L_2 b b^{-1} L_3, \quad S_i = L_1 a a^{-1} L_2 b b^{-1} L_3, \quad S_{i + 1} = L_1 a a^{-1} L_2 L_3 </mathtex>, где <mathtex>L_1, L_2, L_3</mathtex> − некие строки. <br>Таким образом, у нас есть часть цепочки <mathtex>L_1 L_2 b b^{-1} L_3 \rightarrow L_1 a a^{-1} L_2 b b^{-1} L_3 \rightarrow L_1 a a^{-1} L_2 L_3 </mathtex>. Заменим эту часть цепочки на <mathtex>L_1 L_2 b b^{-1} L_3 \rightarrow L_1 L_2 L_3 \rightarrow L_1 a a^{-1} L_2 L_3 </mathtex>. Заметим, что крайние значения части цепочки от этого не изменятся, но <mathtex>\sum |S_i|</mathtex> уменьшится, а это противоречит нашему предположению о минимальности суммы.# Пар, пересекающихся по двум позициям. Тогда <mathtex>S_{i-1} = S_{i+1}</mathtex>, и можно избавиться от <mathtex>S_{i}</mathtex> и <mathtex>S_{i + 1}</mathtex>, и от этого сумма длин слов также уменьшится.# Пар, пересекающихся по одной позиции. Имеем <mathtex>L_1 a L_2 \rightarrow L_1 a a^{-1} a L_2 \rightarrow L_1 a L_2</mathtex>, и в этом случае мы также можем избавиться от <mathtex>S_{i}</mathtex> и <mathtex>S_{i + 1}</mathtex>, что также уменьшит итоговую сумму длин строк.