Building Languages with Set Operations

Hello! Welcome to your third lesson in the Theory of Computation.

In our last lesson, we developed the crucial skill of proving properties of string operations using mathematical induction. We now have a solid grasp on the building blocks (alphabets, strings, languages) and a powerful method for reasoning about them formally.

Today, we will build upon this foundation to achieve this lesson's learning outcome: to construct languages using set operations (union, intersection, complement, concatenation, and Kleene star). We will explore how to combine simple languages into more complex and interesting ones. These operations are not just abstract concepts; they form the very core of tools you've likely used, such as regular expressions for pattern matching in code or text processing pipelines.

Let's begin by exploring these operations, starting with those that are likely already familiar to you from set theory.

1. Set-Theoretic Operations on Languages

Since we defined a language as a set of strings, it follows that we can apply standard set operations to them. The three fundamental set operations are union, intersection, and complement.

Set Operations with Venn Diagrams — Venn diagrams illustrating the set operations of Union, Intersection, Difference (a form of complement), and Complement. For languages, the universal set is $\Sigma^*$, the set of all possible strings over a given alphabet.

Let's consider two languages, $L_{1}$ and $L_{2}$ , over an alphabet $Σ$ .

Union (∪): The union of $L_{1}$ and $L_{2}$ , written as $L_{1} \cup L_{2}$ , is the language containing all strings that are in $L_{1}$ , or in $L_{2}$ , or in both. $L_{1} \cup L_{2} = {w \in Σ^{*} ∣ w \in L_{1} or w \in L_{2}}$
Intersection (∩): The intersection of $L_{1}$ and $L_{2}$ , written as $L_{1} \cap L_{2}$ , is the language containing all strings that are in both $L_{1}$ and $L_{2}$ . $L_{1} \cap L_{2} = {w \in Σ^{*} ∣ w \in L_{1} and w \in L_{2}}$
Complement (L̄): The complement of a language $L$ , written as $L ˉ$ or $L^{c}$ , is the set of all strings over the alphabet $Σ$ that are not in $L$ . It's crucial to remember this is a relative complement with respect to $Σ^{*}$ . $L ˉ = Σ^{*} - L = {w \in Σ^{*} ∣ w \in / L}$

Example:
Let $Σ = {a, b}$ , $L_{1} = {a, ab, aba}$ , and $L_{2} = {b, ab, bab}$ .

$L_{1} \cup L_{2} = {a, b, ab, aba, bab}$
$L_{1} \cap L_{2} = {ab}$
$L_{1} ˉ$ contains every string made of 'a's and 'b's that is not in $L_{1}$ . This is an infinite language. A few of its strings are: $ϵ, b, aa, ba, bb, aaa, aab, ...$

2. Language-Specific Operations

Next, we'll explore operations that are unique to formal languages and leverage the concatenative nature of strings. For a high-level, intuitive overview, the following video is an excellent starting point.

Introduction to Languages, Strings, and Operations

This video from the lydia channel provides clear, animated examples of the key language operations: union, intersection, concatenation, and the star operation. It will help build your intuition before we dive into the formal definitions.

Watch the video from 01:47 to 04:30. Focus on how new languages are constructed from the example languages A and B for each operation, especially for concatenation and the star operation.

Now that you have a visual feel for these operations, let's establish their formal definitions. The following reading from Jean Gallier's notes provides the rigorous definitions we need.

Chapter 1 Basics of Formal Language Theory

This document provides the precise, mathematical definitions for all the operations we are studying in this lesson.

Please read Section 1.3, 'Operations on Languages' (pages 19-24). Start from the heading '1.3 Operations on Languages' and read through to the end of Definition 1.3.2 and its subsequent explanation. Focus on the formal definitions of concatenation, language exponentiation (L^n), and the Kleene closures (L* and L+).

Let's review and expand on the key definitions from the reading.

Language Concatenation

This operation is a natural extension of string concatenation, which we studied in the previous lesson.

Concatenation (·): The concatenation of $L_{1}$ and $L_{2}$ , written as $L_{1} L_{2}$ or $L_{1} \cdot L_{2}$ , is the language formed by taking every string in $L_{1}$ and appending to it every string in $L_{2}$ . $L_{1} L_{2} = {uv ∣ u \in L_{1} and v \in L_{2}}$ Important: Like string concatenation, language concatenation is not commutative. In general, $L_{1} L_{2} \neq = L_{2} L_{1}$ .

Example:
Let $L_{1} = {a, b}$ and $L_{2} = {0, 11}$ .

$L_{1} L_{2} = {a 0, a 11, b 0, b 11}$
$L_{2} L_{1} = {0 a, 0 b, 11 a, 11 b}$

Language Exponentiation and Kleene Closure

These operations allow us to generate languages of infinite size from finite ones, which is a cornerstone of this field.

First, we define the power of a language $L$ , denoted $L^{k}$ , as concatenating the language with itself $k$ times.

$L^{0} = {ϵ}$ (This is a crucial definition: the "zeroth power" of any language is the set containing only the empty string).
$L^{1} = L$
$L^{2} = LL$
In general, $L^{k} = L \cdot L^{k - 1}$ for $k \geq 1$ .

With this, we can define the two most powerful operations: Kleene Star and Kleene Plus.

Kleene Star (∗): The Kleene star (or Kleene closure) of a language $L$ , written as $L^{*}$ , is the union of all powers of $L$ . It represents concatenating zero or more strings from $L$ .
$L^{*} = i = 0 ⋃ \infty L^{i} = L^{0} \cup L^{1} \cup L^{2} \cup \dots$
Since $L^{0} = {ϵ}$ , the language $L^{*}$ always contains the empty string $ϵ$ , regardless of whether $ϵ$ is in $L$ .
Kleene Plus (+): The Kleene plus of $L$ , written as $L^{+}$ , is similar but excludes the $L^{0}$ case. It represents concatenating one or more strings from $L$ .
$L^{+} = i = 1 ⋃ \infty L^{i} = L^{1} \cup L^{2} \cup \dots$
This leads to the simple relationship: $L^{*} = L^{+} \cup {ϵ}$ .

Let's visualize the Kleene Star with an example.

Example of Kleene Star Operation — This image demonstrates the Kleene star operation on the language $L = \{aa, b\}$. It shows how $L^0$, $L^1$, and $L^2$ are formed, and then defines $L^*$ as the infinite union of all such powers. Strings in $L^*$ include $\epsilon$, $aa$, $b$, $aaaa$, $aab$, $baa$, $bb$, and so on.

This operation directly corresponds to the * quantifier in regular expressions. For example, the regex a* describes the language ${a}^{*}$ , which is ${ϵ, a, aa, aaa, \dots}$ .

3. Putting It All Together

Let's work through an example that combines these operations.

Let $Σ = {0, 1}$ .
Let $L_{1} = {0, 1}$ (this is just $Σ$ itself).
Let $L_{2} = {00, 11}$ .

$L_{1}^{*}$ : This is the set of all strings that can be formed by concatenating zero or more symbols from ${0, 1}$ . This is simply $Σ^{*}$ , the set of all possible binary strings.
$L_{2}^{+}$ : This is the set of all strings formed by concatenating one or more strings from ${00, 11}$ .
- $L_{2}^{1} = {00, 11}$
- $L_{2}^{2} = {0000, 0011, 1100, 1111}$
- $L_{2}^{+}$ includes all of these and more, like $110011, 000000$ , etc. Notice that every string in $L_{2}^{+}$ has an even length.
$L_{1} L_{2}$ : ${0, 1} {00, 11} = {000, 011, 100, 111}$ . This is the set of all 3-bit binary numbers.
$(L_{1} \cup L_{2})^{*}$ :
- $L_{1} \cup L_{2} = {0, 1, 00, 11}$ .
- The star of this set includes $ϵ$ , any string from the set itself (like 0 or 11), and any concatenation of them (like 011, 110, 0010). This language is also equivalent to $Σ^{*}$ . Why? Because 0 and 1 are in the base set, any binary string can be formed.

Test your understanding!

Let $Σ = {a, b}$ , $L_{A} = {a, ϵ}$ , and $L_{B} = {b}$ .

Calculate the following languages. List at least 4-5 strings for any infinite languages.

$L_{A} \cap L_{B}$
$L_{B}$
$L_{A} L_{B}$
$L_{B}^{+}$
$L_{A}^{*}$

Show answer

$L_{A} \cap L_{B}$ : The intersection contains elements present in both sets. There are no common strings.
$L_{A} \cap L_{B} = \emptyset$
$L_{B}$ : The complement of ${b}$ is every string in $Σ^{*}$ except for 'b'.
$L_{B} = {ϵ, a, aa, ab, ba, bb, aaa, \dots}$
$L_{A} L_{B}$ : We concatenate each string from $L_{A}$ with each from $L_{B}$ .
$L_{A} L_{B} = {a \cdot b, ϵ \cdot b} = {ab, b}$
$L_{B}^{+}$ : This is one or more concatenations of the string 'b'.
$L_{B}^{+} = {b, bb, bbb, bbbb, \dots}$
$L_{A}^{*}$ : This is zero or more concatenations of strings from ${a, ϵ}$ . Since concatenating with $ϵ$ doesn't change a string ( $a ϵ = a$ , $ϵϵ = ϵ$ ), this is equivalent to zero or more concatenations of just 'a'.
$L_{A}^{*} = {a}^{*} = {ϵ, a, aa, aaa, aaaa, \dots}$

Conclusion

In this lesson, we have equipped ourselves with a powerful toolkit for constructing and describing languages.

Key Takeaways:

Languages can be combined using standard set operations: union (∪), intersection (∩), and complement (L̄). The complement is always taken with respect to $Σ^{*}$ .
Languages also have special operations based on string structure: concatenation (L₁L₂) and the powerful closure operations.
Kleene Star (L)* generates the set of all strings formed by concatenating zero or more elements of a language L. It always includes $ϵ$ .
Kleene Plus (L+) generates the set of all strings formed by concatenating one or more elements of L.

These operations are the verbs of our formal language theory. They allow us to precisely define languages, including infinite ones, from simple, finite building blocks.

In the next lesson, we will formalize the distinction between finite and infinite languages and introduce our first computational model: the automaton. We will see that these operations are not just for description; they are intimately connected to what simple machines can—and cannot—compute.

Recommended resources