WikiSort.ru - Программирование

Свойства конкатенации

• Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: ${\displaystyle (wiki\cdot media)\cdot pedia=wikimediapedia}$ , и в то же время ${\displaystyle wiki\cdot (media\cdot pedia)=wikimediapedia}$ .
• Операция конкатенации некоммутативна. В самом деле, ${\displaystyle wiki\cdot media=wikimedia}$ , но ${\displaystyle media\cdot wiki=mediawiki\neq wikimedia}$ . От перестановки операндов меняется результат операции, что и означает её некоммутативность.
• Пустое слово — ${\displaystyle \varepsilon }$ , — является нейтральным элементом (единицей) операции конкатенации. То есть, если ${\displaystyle \varepsilon }$  — пустое слово, то для любого слова ${\displaystyle \alpha }$ выполнено равенство:

• Множество ${\displaystyle A^{*}}$ всех слов в алфавите образует моноид (так называемый «свободный моноид»).
• Множество ${\displaystyle A^{*}\setminus \{\varepsilon \}}$ всех непустых слов в алфавите образует полугруппу.
• Длина (количество букв) конкатенации слов равна сумме длин операндов:

Итерации

Операция конкатенации слов, подобно операции умножения чисел, порождает операцию итерации (или «возведения в степень»). Пусть ${\displaystyle \alpha }$  — некоторое слово в алфавите ${\displaystyle A}$ , а ${\displaystyle n}$  — целое неотрицательное число. Тогда ${\displaystyle n}$ -ой степенью слова ${\displaystyle \alpha }$ , обозначаемой ${\displaystyle \alpha ^{n}}$ , будет слово ${\displaystyle \gamma }$ в том же алфавите ${\displaystyle A}$ , определяемое равенством:

(повтор слова ${\displaystyle \alpha }$ ${\displaystyle n}$ раз). Пример: «a»³="aaa".

В случае ${\displaystyle n=0}$ , степень ${\displaystyle \alpha ^{0}}$ по определению полагается равной пустому слову, ${\displaystyle \varepsilon }$ .