String and Language Operations

In our previous lesson, we established the formal vocabulary of alphabets, strings, and languages. This provided us with a mathematical framework for describing sets of sequences, which in turn represent computational problems. Now, we will build upon that foundation by learning how to construct new, more complex languages from existing ones.

This lesson focuses on the three fundamental operations on languages: union, concatenation, and the Kleene star. These operations form a powerful toolkit for defining and manipulating languages. Mastering them is essential, as they are the building blocks for regular expressions and are intrinsically linked to the capabilities of the finite automata we will begin studying in the next lesson.

From String to Language Operations

Before we operate on entire languages (which are sets of strings), let's first formalize the most basic operation between individual strings: concatenation.

Definition: String Concatenation
Given two strings $x$ and $y$ over an alphabet $Σ$ , their concatenation, written as $x y$ , is the string formed by appending $y$ to the end of $x$ .

Given your background in mathematics, a more formal definition will be satisfying. If we define a string $x$ of length $m$ as a function $x : {1, \dots, m} \to Σ$ and a string $y$ of length $n$ as a function $y : {1, \dots, n} \to Σ$ , their concatenation $w = x y$ is a new string of length $m + n$ defined as:

w (j) = {x (j) y (j - m) if 1 \leq j \leq m if m + 1 \leq j \leq m + n

This definition precisely captures the idea of placing the symbols of $y$ immediately after the symbols of $x$ . Key properties of string concatenation include:

Associativity: $(uv) w = u (v w)$ for any strings $u, v, w$ .
Identity Element: The empty string $ϵ$ is the identity for concatenation: $w ϵ = ϵ w = w$ for any string $w$ .

With this string-level operation in hand, we can now "lift" it to the level of languages and introduce the other core operations.

The Regular Operations

The three operations of union, concatenation, and Kleene star are so fundamental to this field that they are collectively known as the regular operations.

Regular operations and regular expressions

This document from the University of Waterloo provides concise, formal definitions for the three regular operations on languages.

Please read the definitions for Union and Concatenation. Then, read the definition for Kleene star. Focus on understanding how each operation produces a new language (a set of strings) from one or two input languages.

Let's examine each of these operations in more detail, with examples to solidify your understanding.

1. Union

As you've already seen from your set theory background, the union of two languages $A$ and $B$ , written $A \cup B$ , is simply the set of all strings that are in $A$ , or in $B$ , or in both.
$A \cup B = {w ∣ w \in A or w \in B}$
For example, if $L_{1} = {0, 00}$ and $L_{2} = {1, 11}$ , then $L_{1} \cup L_{2} = {0, 00, 1, 11}$ .

2. Concatenation

Language concatenation builds directly on string concatenation. The concatenation of two languages $A$ and $B$ , written $A B$ , is the set of all strings that can be formed by taking any string from $A$ and concatenating it with any string from $B$ .
$A B = {w x ∣ w \in A and x \in B}$
Crucially, the order matters. The string from $A$ must come first. This means that, in general, $A B \neq = B A$ . Concatenation is not commutative.

The image below gives a clear visual summary for the concatenation of two sets of strings, A and B.

This image illustrates the formal definitions and examples for language concatenation (AB) and the Kleene closure (A*). For concatenation, notice how every string in A is paired with every string in B.

Let's watch a short video that walks through a concrete example of both union and concatenation.

Operations on Regular Languages

This video from Neso Academy clearly demonstrates how to perform these operations on two finite languages.

Watch the segment from perform Union, where the presenter calculates A U B and A concatenated with B for specific sets A and B.

3. Kleene Star (or Kleene Closure)

The Kleene star is perhaps the most powerful of the three operations. The star of a language $A$ , written $A^{*}$ , is the set of all strings that can be formed by taking any number of strings from $A$ (including zero) and concatenating them together.

The formal definition can be expressed as an infinite union:
$A^{*} = ⋃_{i = 0}^{\infty} A^{i} = A^{0} \cup A^{1} \cup A^{2} \cup \dots$
Here, $A^{i}$ represents the language formed by concatenating $i$ strings from $A$ .

$A^{0} = {ϵ}$ (the concatenation of zero strings is defined as the empty string).
$A^{1} = A$
$A^{2} = AA$
...and so on.

A critical consequence of this definition is that for any language $A$ , the empty string $ϵ$ is always an element of $A^{*}$ , because it is always in $A^{0}$ .

The visual summary you saw earlier also provides a clear definition of the Kleene Closure. Note the summation-style notation which is equivalent to the infinite union.

A related operation is the positive closure, denoted $A^{+}$ , which is the set of strings formed by concatenating one or more strings from $A$ .
$A^{+} = ⋃_{i = 1}^{\infty} A^{i} = A^{1} \cup A^{2} \cup A^{3} \cup \dots$
The relationship between the two is straightforward:

$A^{*} = A^{+} \cup {ϵ}$
$A^{+} = A A^{*}$

Now, let's see an example of the Kleene star operation.

Operations on Regular Languages

Continuing with the same video, let's see the star operation applied.

Watch the segment from a star. Pay close attention to how strings are formed by choosing elements from the set A multiple times and in different orders, and note the inclusion of \epsilon.

Practice Exercise

To put these definitions into practice, consider the following languages over the alphabet $Σ = {a, b}$ :

$L_{1} = {a, b}$
$L_{2} = {ab, ba}$

Determine the elements of the following languages. Take a moment to write them down before revealing the solution.

$L_{1} \cup L_{2}$
$L_{1} L_{2}$
$L_{2} L_{1}$
$L_{1}^{*}$ (List at least 8 distinct strings)

Solution

$L_{1} \cup L_{2}$ : This is the set of all strings present in either language.
$L_{1} \cup L_{2} = {a, b, ab, ba}$
$L_{1} L_{2}$ : We take each string from $L_{1}$ and append each string from $L_{2}$ .
- a from $L_{1}$ + ab from $L_{2}$ $\to$ aab
- a from $L_{1}$ + ba from $L_{2}$ $\to$ aba
- b from $L_{1}$ + ab from $L_{2}$ $\to$ bab
- b from $L_{1}$ + ba from $L_{2}$ $\to$ bba
  $L_{1} L_{2} = {aab, aba, bab, bba}$
$L_{2} L_{1}$ : We take each string from $L_{2}$ and append each string from $L_{1}$ . Notice this demonstrates non-commutativity.
- ab from $L_{2}$ + a from $L_{1}$ $\to$ aba
- ab from $L_{2}$ + b from $L_{1}$ $\to$ abb
- ba from $L_{2}$ + a from $L_{1}$ $\to$ baa
- ba from $L_{2}$ + b from $L_{1}$ $\to$ bab
  $L_{2} L_{1} = {aba, abb, baa, bab}$
  (Note: $L_{1} L_{2} \neq = L_{2} L_{1}$ )
$L_{1}^{*}$ : The set of all strings made by concatenating zero or more strings from $L_{1} = {a, b}$ .
- Zero strings: $ϵ$
- One string: $a, b$
- Two strings: $aa, ab, ba, bb$
- Three strings: $aaa, aab, aba, abb, baa, bab, bba, bbb$
  ...and so on. In fact, $L_{1}^{*}$ is the set of all possible strings over the alphabet ${a, b}$ , which we previously denoted as $Σ^{*}$ .
  A sample of strings in $L_{1}^{*}$ is:
  ${ϵ, a, b, aa, ab, ba, bb, aaa, aab, \dots}$

Conclusion

In this lesson, we have defined and practiced the three regular operations—union, concatenation, and Kleene star—which allow us to combine and construct languages in powerful ways.

Here are the key takeaways:

Union ( $\cup$ ) combines the strings from two languages into a single larger language, just like set union.
Concatenation ( $L_{1} L_{2}$ ) creates a new language by appending each string of $L_{2}$ to each string of $L_{1}$ . The order is crucial, and the operation is not commutative.
Kleene Star ( $L^{*}$ ) generates an infinite language containing all possible strings formed by concatenating zero or more strings from $L$ . The empty string, $ϵ$ , is always a member of $L^{*}$ .

These operations are not just abstract definitions. They form the algebraic basis for regular expressions, a powerful text-matching tool you may have encountered in programming. More importantly for this course, they exactly characterize the descriptive power of our first class of computational models.

In the next lesson, we will formally define the Deterministic Finite Automaton (DFA). We will see that the set of all languages that can be recognized by a DFA—the "regular languages"—is precisely the set of languages that can be built up from simple starting blocks using these three operations.

Recommended resources