Course contentsShow
← Computer Science
Lesson 1758 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

String Operations: Concatenation

Define string concatenation, its properties (associativity, identity element), and notation conventions.

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.