String Operations: Concatenation
You'll learn: How to combine strings using concatenation, including its formal properties and notation in formal language theory.
What is String Concatenation?
Concatenation is the operation of joining two strings end-to-end to form a new string. If you have string x = "hello" and string y = "world", their concatenation xy = "helloworld" places every symbol of y immediately after the last symbol of x.
Think of it like linking train cars together: the first string forms the front cars, and the second string attaches directly behind.
Formal Definition and Notation
Given strings x and y over some alphabet, their concatenation is written as:
xy(most common, no operator needed)x · y(explicit dot operator)x + y(in some contexts)
For example, if x = "cat" and y = "fish", then xy = "catfish".
Key Properties
Associativity: Concatenation is associative: (xy)z = x(yz). The grouping doesn't matter when combining three or more strings.
Identity Element: The empty string ε acts as the identity: xε = εx = x. Concatenating nothing leaves the string unchanged.
Not Commutative: Unlike addition, order matters! xy ≠ yx in general. "hello" + "world" gives a different result than "world" + "hello".
Why It Matters in Theory of Computation
Concatenation is fundamental to defining languages. A language is a set of strings, and operations like concatenation let us describe how to build complex languages from simpler ones—essential for understanding regular expressions and formal grammars.
Key Takeaway: String concatenation joins strings sequentially; it's associative with the empty string as identity, but not commutative.