Formal Definitions: Alphabets, Strings, and Languages

The Bedrock of Computation: Formal Languages

In computer science, when we talk about a "language," we aren't just referring to human languages like English or programming languages like Java. We're using a more abstract and powerful concept: a formal language. At its core, a formal language is a way to precisely define a set of valid sequences, which we call strings. The theory of computation is deeply intertwined with the study of these formal languages, as recognizing whether a string belongs to a particular language is equivalent to solving a computational problem.

To get a feel for these foundational ideas, let's watch a short segment from a video by GATE Applied Course. It will introduce the key terms we'll be defining today.

As the video explained, these definitions build on one another. Let's formalize each one.

1. Alphabets: The Symbols of Discourse

The most basic component of any language is its set of symbols. In formal language theory, this is called an alphabet.

Definition: Alphabet
An alphabet is a non-empty, finite set of symbols. We typically denote an alphabet using the Greek letter sigma, $\Sigma$.

Here are some common examples:

• The binary alphabet: $\Sigma =\{0,1\}$
• The lowercase English alphabet: $\Sigma =\{a,b,c,\dots ,z\}$
• The alphabet of decimal digits: $\Sigma =\{0,1,2,\dots ,9\}$

The key constraints are that the set must be finite and non-empty. The image below, from a Princeton CS course, illustrates various alphabets and the corresponding names for their symbols and strings.

2. Strings: Sequences of Symbols

Once we have an alphabet, we can form strings by creating sequences of its symbols.

Definition: String
A string over an alphabet $\Sigma$ is a finite sequence of symbols drawn from $\Sigma$.

For example, if $\Sigma =\{a,b\}$, then a, baba, and bbbaaa are all strings over $\Sigma$.

Given your mathematical background, you'll appreciate a more rigorous definition that avoids the ambiguity of the word "sequence." We can define a string as a function.

This functional definition is elegant because it formalizes what we mean by a symbol being at a certain "position" in the string. Let's solidify a few related concepts:

• Length of a String: The length of a string $w$, denoted $|w|$, is the number of symbols in it. If $w$ is defined as a function $w:[n]\to \Sigma$, its length is simply $n$. For example, $|1011|=4$.
• The Empty String: There is one special string, the empty string, which has a length of 0. It is denoted by $ϵ$ (epsilon) or sometimes $\lambda$ (lambda). It is the unique string containing no symbols. In the functional definition, it corresponds to the function from the empty set: $ϵ:[0]\to \Sigma$.
• The Set of All Strings (Kleene Star): For a given alphabet $\Sigma$, the set of all possible strings (of any finite length) that can be formed from it is denoted by ${\Sigma }^{\ast }$. This is a foundational concept known as the Kleene star or Kleene closure of the alphabet. For example, if $\Sigma =\{0,1\}$, then ${\Sigma }^{\ast }=\{ϵ,0,1,00,01,10,11,000,\dots \}$. Note that ${\Sigma }^{\ast }$ is always an infinite set (unless $\Sigma$ is the empty set, which we typically don't allow for alphabets).

3. Languages: Sets of Strings

Now we arrive at the final and most important definition. With our universe of all possible strings, ${\Sigma }^{\ast }$, we can define precisely what a language is.

Definition: Language
A language $L$ over an alphabet $\Sigma$ is any subset of ${\Sigma }^{\ast }$. In other words, $L\subseteq {\Sigma }^{\ast }$.

This definition is both simple and incredibly powerful. A language is just a set of strings. This set can be finite, infinite, or even empty. The "rules" of a language (like grammar in English) are simply the criteria that determine which strings from ${\Sigma }^{\ast }$ are included in the set $L$.

This image shows several examples of languages over the binary alphabet $\Sigma =\{a,b\}$.

Let's look at the second example, "equal numbers of as and bs". Using set-builder notation, we can formally write this language as:
$L=\{w\in \{a,b{\}}^{\ast }\mid \text{the number of }a\text{’s in }w\text{ equals the number of }b\text{’s in }w\}$
Strings like ba, bbaaba, and ϵ are in this language, while a and abbaa are not.

A Point of Clarification: Nothing, Emptiness, and a Language of Emptiness

It is crucial to distinguish between three related concepts that often cause confusion.

1. The empty string, $ϵ$, is a string of length zero. It is a single, concrete object.
2. The empty set, $\varnothing$, is a set containing zero elements. When we talk about languages, this corresponds to the empty language $L=\varnothing$, which is a language with no strings in it.
3. The language containing only the empty string is the set $\{ϵ\}$. This is a non-empty language; it has one member, which happens to be the empty string.

Let's watch a brief clip where this distinction is explained clearly.

Why Formalize Languages? The Link to Computation

You might be wondering why we've spent this time on what seem like simple definitions. The power of this framework lies in its ability to rephrase any computational decision problem as a language membership problem.

A decision problem is any problem that has a yes/no answer. For example: "Is the number n a prime number?"

We can encode the input to such a problem as a string. Then, the language associated with the problem is the set of all input strings for which the answer is "yes."

As the notes explain, if we can build a machine (an automaton) that, for any given string $w$, can correctly answer whether $w\in L$, then we have effectively solved the computational problem that $L$ represents. This is the central theme of this course. We will study different types of machines and discover which classes of languages they are capable of "recognizing" or "deciding."

Conclusion

In this introductory lesson, we have laid the formal groundwork for our study of computation. We established a precise hierarchy of concepts:

• An alphabet $\Sigma$ is a finite set of symbols.
• A string is a finite sequence of symbols from an alphabet. The set of all possible strings is ${\Sigma }^{\ast }$.
• A language $L$ is any subset of ${\Sigma }^{\ast }$.

The key takeaway is that computational problems can be reframed as questions of whether a string belongs to a particular language. This abstraction allows us to apply the rigorous tools of mathematics to analyze the fundamental nature of computation itself.

In our next lesson, we will continue building our toolkit by exploring the fundamental operations used to construct new strings and languages from existing ones, such as concatenation, union, and the Kleene star operation. These operations will be essential for defining and understanding regular languages, our first major topic.