Эта статья требует доработки!
- Необходимо добавить примеры (из тех, что были у нас в качестве задач)(исправлено)
Если Вы исправили некоторые из указанных выше замечаний, просьба дописать в начало соответствующего пункта (Исправлено).
Свободная группа
Рассмотрим конечный алфавит [math] \Sigma = \{ a_1, a_2, \dots a_n \}, \; \Sigma^{-1} = \{ a_1^{-1}, a_2^{-1}, \dots a_n^{-1} \} [/math].
Рассмотрим множество строк над алфавитом [math] \Sigma \cup \Sigma^{-1} ; \; S = S_1 S_2 \dots S_k , \; символ a \in \Sigma \cup \Sigma^{-1} [/math].
| Определение: |
| [math]S[/math] и [math]S'[/math] называются эквивалентными, если они могут быть превращены друг в друга вставками и удалениями из произвольных мест [math]aa^{-1}[/math] и [math]a^{-1}a[/math]. |
Таким образом, [math] \Sigma \cup \Sigma^{-1} [/math] с операцией конкатенации будет группой (обратным элементом будет обращение строки с заменой всех символов на «обратные» им).
| Определение: |
| [math] \Sigma \cup \Sigma^{-1} [/math] называется свободной группой, порожденной алфавитом [math]\Sigma[/math]. |
Рассмотрим строку. Проредуцируем её (будем последовательно удалять [math]aa^{-1}[/math] из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?
| Теорема (О редуцированной строке): |
У одной строки существует лишь одна редуцированная строка |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть существуют 2 проредуцированные строки [math]\omega_1[/math] и [math]\omega_2[/math], заданные одной строкой. Тогда существуют цепочки вставок и удалений
[math]\omega_1 \rightarrow S_1 \rightarrow S_2 \dots \rightarrow S_k \rightarrow \omega_2 [/math], где [math]\rightarrow[/math] − операция вставки или удаления [math]aa^{-1}[/math]. (Существование цепочки обеспечено тем, что эти строки образованы одним элементом).
Среди цепочек рассмотрим такую, у которой минимально [math]\sum |S_i|[/math] и пусть [math]S_i[/math] − строка наибольшей длины.
Рассмотрим [math] S_{i - 1} \rightarrow S_i \rightarrow S_{i + 1} [/math], причем мы знаем, что переходы от [math]i[/math] к [math]i - 1[/math] и [math]i + 1[/math] обеспечены за счет удаления (из-за того, что длина [math]S_i[/math] максимальна). Эти переходы могут быть обеспечены за счет:
- Двух непересекающихся пар. Тогда пусть [math] 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 [/math], где [math]L_1, L_2, L_3[/math] − некие строки.
Таким образом, у нас есть часть цепочки [math]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 [/math]. Заменим эту часть цепочки на [math]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 [/math]. Заметим, что крайние значения части цепочки от этого не изменятся, но [math]\sum |S_i|[/math] уменьшится, а это противоречит нашему предположению о минимальности суммы.
- Пар, пересекающихся по двум позициям. Тогда [math]S_{i-1} = S_{i+1}[/math], и можно избавиться от [math]S_{i}[/math] и [math]S_{i + 1}[/math], и от этого сумма длин слов также уменьшится.
- Пар, пересекающихся по одной позиции. Имеем [math]L_1 a L_2 \rightarrow L_1 a a^{-1} a L_2 \rightarrow L_1 a L_2[/math], и в этом случае мы также можем избавиться от [math]S_{i}[/math] и [math]S_{i + 1}[/math], что также уменьшит итоговую сумму длин строк.
Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему. |
| [math]\triangleleft[/math] |
Задание группы определяющими соотношениями
Пусть также имеем алфавит [math]\Sigma = \{ a_1, \dots a_n \} [/math] и набор пар строк [math]S_1 \sim \omega_1, \dots, S_n \sim \omega_n[/math]. Разрешается где угодно менять [math]\omega_i[/math] на [math]S_i[/math] и наоборот.
| Определение: |
| Выражения [math]S_1 \sim \omega_1, \dots, S_n \sim \omega_n[/math] называются определяющими соотношениями. |
| Утверждение (без доказательства): |
Задача проверки эквивалентности строк при заданных определяющих соотношениях алгоритмически неразрешима. |
пример решения задачи
Пример группы G[math]=\{a[/math], [math]b|aba=b[/math], [math]bab=a\}[/math]. докажем что:
1)[math]a^2=b^2[/math]
2)[math]a^4=b^4=e[/math]
3)[math]|G|=8[/math]
доказательство:
1) [math]aba=b \Rightarrow a(bab)=bb[/math] подставляем из второго условия группы и получаем: [math] aa=bb \Rightarrow a^2=b^2[/math]
2) [math]aba=b \Rightarrow ba=a^{-1}b[/math], [math]bab=a \Rightarrow ab=b^{-1}a[/math], перемножаем, получаем:[math]abba=e[/math], но из доказанного ранее [math]a^2=b^2 \Rightarrow a^4=e[/math] и [math]b^4=e[/math]
3)Рассмотрим все последовательности из [math]3[/math] элементов: их [math]8[/math]. Заметим, что есть последовательности из [math]3[/math] одинаковых элементов[math](ааа[/math], [math]bbb)[/math], из [math]2[/math] подряд идущих одинаковых и одного отличного[math](aab[/math], [math]bba[/math], [math]baa[/math], [math]abb)[/math] и [math]aba[/math], [math]bab[/math]. Но [math]b^2=a^2[/math], поэтому [math]aab=baa=b^3[/math], [math]bba=abb=a^3[/math], а [math]aba=b[/math], [math]bab=a[/math], поэтому все тройки равны либо третьей либо первой степени [math]a[/math] или [math]b[/math]. Из таблицы умножения(приведена далее) видно, что произведения приведенной далее видно, что произведение последовательности длинное три(те [math]a^3[/math],[math]b^3[/math], [math]a[/math], [math]b[/math]) не выходит за ее пределы. Те последовательность большей длинны по правилам умножения, задания [math]G[/math] и доказанных равенств будет сокращаться до последовательности длины [math]\lt =2[/math] или [math]a^3[/math] или [math]b^3 \Rightarrow |G|=8[/math]
запишем таблицу умножения для [math]G[/math]:
| *
|
e
|
a
|
b
|
ab
|
ba
|
aa
|
aaa
|
bbb
|
| e
|
e |
a |
b |
ab |
ba |
aa |
aaa |
bbb
|
| a
|
a |
aa |
ab |
bbb |
b |
aaa |
e |
ba
|
| b
|
b |
ba |
aa |
a |
ab |
|
|
|
| ab
|
ab |
b |
aaa |
aa |
e |
|
|
|
| ba
|
ba |
bbb |
a |
e |
bb |
|
|
|
| aa
|
aa |
aaa |
bbb |
ba |
ab |
|
|
|
| aaa
|
aaa |
e |
ba |
b |
|
|
|
|
bbb
|
bbb |
ab |
e |
aaa |
|
|
|
|
