Представление групп

Эта статья находится в разработке!

Свободная группа

Рассмотрим конечный алфавит [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] из нее, пока в строке не будет таких последовательностей элементов). Поставим вопрос: правда ли, что вне зависимости от последовательности удалений мы будем получать одну и ту же конечную редуцированную строку?