Меню Главная Случайная статья Настройки Конкатенация Материал из https://ru.wikipedia.org Конкатенация (лат. concatenatio «присоединение цепями; сцепление») — операция склеивания объектов линейной структуры[1], обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир». Содержание 1 В математике 1.1 Свойства конкатенации 1.2 Итерации 2 В информатике 3 См. также 4 Примечания В математике Конкатенация — бинарная операция, определённая на словах данного алфавита. Обозначения: ${\displaystyle A}$ — алфавит, набор букв; ${\displaystyle \alpha }$, ${\displaystyle \beta }$, ${\displaystyle \gamma }$ — слова, составленные из букв; ${\displaystyle a_{1}\ldots a_{n}}$ и ${\displaystyle b_{1}\ldots b_{m}}$ — записанные подряд и пронумерованные буквы двух слов. Если ${\displaystyle \alpha =a_{1}\ldots a_{n}}$ и ${\displaystyle \beta =b_{1}\ldots b_{m}}$ — слова из алфавита ${\displaystyle A}$, то конкатенацией слов ${\displaystyle \alpha }$ и ${\displaystyle \beta }$, которую обозначим в этой статье как ${\displaystyle \alpha \cdot \beta }$, будет слово ${\displaystyle \gamma }$ из того же алфавита ${\displaystyle A}$, определяемое равенством ${\displaystyle \gamma =\alpha \cdot \beta =a_{1}\ldots a_{n}b_{1}\ldots b_{m}}$. Например, если ${\displaystyle \alpha =media}$ и ${\displaystyle \beta =wiki}$ — слова из алфавита ${\displaystyle A=\{a,b,c,\ldots ,z\}}$, содержащем все буквы латинского алфавита, то ${\displaystyle \gamma =\alpha \cdot \beta =media\cdot wiki=mediawiki}$. Свойства конкатенации Операция конкатенации ассоциативна. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: ${\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 \varepsilon \cdot \alpha =\alpha \cdot \varepsilon =\alpha }$. Множество ${\displaystyle A^{*}}$ всех слов в алфавите образует моноид (так называемый «свободный моноид»[англ.]). Множество ${\displaystyle A^{*}\setminus \{\varepsilon \}}$ всех непустых слов в алфавите образует полугруппу. Длина (количество букв) конкатенации слов равна сумме длин операндов: ${\displaystyle |\alpha \cdot \beta |=|\alpha |+|\beta |}$. Итерации Операция конкатенации слов, подобно операции умножения чисел, порождает операцию итерации (или возведения в степень). Пусть ${\displaystyle \alpha }$ — некоторое слово из алфавита ${\displaystyle A}$, а ${\displaystyle n}$ — целое неотрицательное число. Тогда ${\displaystyle n}$-ой степенью слова ${\displaystyle \alpha }$, обозначаемой ${\displaystyle \alpha ^{n}}$, будет слово ${\displaystyle \gamma }$ в том же алфавите ${\displaystyle A}$, определяемое равенством: ${\displaystyle {\begin{matrix}\gamma =\alpha ^{n}=&\underbrace {\alpha \cdot \ldots \cdot \alpha } \\&n\end{matrix}}}$ (повтор слова ${\displaystyle \alpha }$ ${\displaystyle n}$ раз). Пример: «a»3=«aaa». В случае ${\displaystyle n=0}$, степень ${\displaystyle \alpha ^{0}}$ по определению полагается равной пустому слову, ${\displaystyle \varepsilon }$. В информатике Операция конкатенации определяется для типов данных, имеющих структуру последовательности (список, очередь, массив и ряд других).В общем случае, результатом конкатенации двух объектов ${\displaystyle A}$ и ${\displaystyle B}$ является объект ${\displaystyle C=A\cdot B}$[2], полученный поочерёдным добавлением всех элементов объекта ${\displaystyle B}$, начиная с первого, в конец объекта ${\displaystyle A}$. Из соображений удобства и эффективности различают две формы операции конкатенации: Модифицирующая конкатенация. Результат операции формируется в левом операнде. Немодифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными. См. также Перебор по словарю Примечания Борзенко Владимир Игоревич. Кратная конкатенация (рус.) // Школа №1553 им. В.И. Вернадского. — 2024. — С. 1. Александр Охотин. [https://users.math-cs.spbu.ru/~okhotin/teaching/tcs3_2018/okhotin_tcs3_2018_l1.pdf Формальные языки и действия над ними. Регулярные выражения. Детерминированные и недетерминированные конечные автоматы. Детерминизация недетерминированных автоматов, преобразование регулярных выражений к автоматам] (неопр.). — 2018. — С. 2. — 12 с. Архивировано 20 декабря 2024 года.