Sammenkædning

Sammenkædning ( lat. concatenatio "vedhæftning ved kæder; sammenkædning") er operationen af limning af objekter med en lineær struktur, normalt strenge . For eksempel vil sammenkædningen af ordene "mikro" og "verden" give ordet "mikroverden".

I matematik

Sammenkædning er en binær operation defineret på ordene i et givet alfabet . Betegnelser:

$EN$ - alfabet, et sæt bogstaver;
$\alfa$ , , - ord bestående af bogstaver; $\beta$ $\gamma$
$a_{1}\ldots a_{n}$ og - skrevet på række og nummererede bogstaver af to ord. $b_{1}\ldots b_{m}$

Hvis og er ord i alfabetet , så er sammenkædningen af ord og , som vi i denne artikel betegner som , et ord i det samme alfabet , defineret af ligheden ${\displaystyle \alpha =a_{1}\ldots a_{n))$ ${\displaystyle \beta =b_{1}\ldots b_{m))$ $EN$ $\alfa$ $\beta$ $\alpha \cdot \beta$ $\gamma$ $EN$

${\displaystyle \gamma =\alpha \cdot \beta =a_{1}\ldots a_{n}b_{1}\ldots b_{m))$ .

For eksempel, hvis og er ord i et alfabet , der indeholder alle bogstaver i det latinske alfabet , så $\alpha =medie$ $\beta =wiki$ ${\displaystyle A=\{a,b,c,\ldots ,z\))$

$\gamma=\alpha \cdot \beta=media\cdot wiki=mediawiki$ .

Sammenkædningsegenskaber

Sammenkædningsoperationen er associativ . Det vil sige, at hvis du har brug for at sammenkæde tre ord, så ændres resultatet ikke fra placeringen af parenteser: , og på samme tid . $(wiki\cdotmedia)\cdotpedia=wikimediapedia$ $wiki\cdot (media\cdot pedia)=wikimediapedia$
Sammenkædningsoperationen er ikke -kommutativ . Faktisk , men . Fra permutationen af operanderne ændres resultatet af operationen, hvilket betyder dens ikke-kommutativitet. $wiki\cdotmedia=wikimedia$ $media\cdot wiki=mediawiki\neq wikimedia$
Det tomme ord - , - er et neutralt element (enhed) i sammenkædningsoperationen. Det vil sige, hvis er et tomt ord, så gælder ligheden for ethvert ord: $\varepsilon$ $\varepsilon$ $\alfa$

$\varepsilon \cdot \alpha =\alpha \cdot \varepsilon =\alpha$ .

Mængden af alle ord i alfabetet danner en monoid (den såkaldte "fri monoid" ). $A^{*}$
Sættet af alle ikke-tomme ord i alfabetet danner en halvgruppe . ${\displaystyle A^{*}\setminus \{\varepsilon \))$
Længden (antal bogstaver) af sammenkædningen af ord er lig med summen af længderne af operanderne:

$|\alpha \cdot \beta |=|\alpha |+|\beta |$ .

Gentagelser

Operationen af sammenkædning af ord, ligesom operationen med multiplikation af tal , genererer operationen af iteration (eller "hæve til en potens") . Lad være et ord i alfabetet , og vær et ikke-negativt heltal . Så vil den th potens af ordet , betegnet med , være ordet i det samme alfabet , defineret af ligheden: $\alfa$ $EN$ $n$ $n$ $\alfa$ ${\displaystyle \alpha ^{n))$ $\gamma$ $EN$

${\begin{matrix}\gamma =\alpha ^{n}=&\underbrace {\alpha \cdot \ldots \cdot \alpha}\\&n\end{matrix))$

(gentag ordet én gang). Eksempel: "a" 3 ="aaa". $\alfa$ $n$

I tilfældet er graden per definition lig med det tomme ord . $n=0$ $\alpha ^{0}$ $\varepsilon$

I datalogi

Sammenkædningsoperationen er defineret for datatyper , der har en sekvensstruktur ( liste , kø , array og en række andre). I det generelle tilfælde er resultatet af sammenkædningen af to objekter det objekt , der opnås ved sekventielt at tilføje alle elementerne i objektet , begyndende fra det første til slutningen af objektet . $EN$ $B$ $C=A\cdot B$ $B$ $EN$

Af bekvemmeligheds- og effektivitetshensyn skelnes der mellem to former for sammenkædningsoperationen:

Ændring af sammenkædning. Resultatet af operationen dannes i venstre operand.
Ikke-modificerende sammenkædning. Resultatet er et nyt objekt, operanderne forbliver uændrede.

Se også

Ordbogssøgning