Fundamentals of Formal Languages

1. Alphabets: The Building Blocks

In any language, whether it's English, Python, or a formal language, we start with a set of basic symbols. In the theory of computation, we call this an alphabet.

An alphabet is a finite, non-empty set of symbols. We conventionally use the uppercase Greek letter Sigma, $\Sigma$, to denote an alphabet.

The symbols themselves are considered atomic or indivisible. What they are doesn't matter as much as the fact that they are distinct elements in a set.

Common Examples:

• The binary alphabet: $\Sigma =\{0,1\}$. This is the fundamental alphabet of all digital computers.
• The alphabet of lowercase English letters: $\Sigma =\{a,b,c,\dots ,z\}$.
• The set of all ASCII characters can be an alphabet.
• A unary alphabet: $\Sigma =\{a\}$. While simple, it's useful for illustrating certain theoretical concepts.

For a rigorous, mathematical definition of an alphabet and its properties, please read the following short text.

2. Strings: Sequences of Symbols

Once we have an alphabet, we can create strings by forming finite sequences of symbols from that alphabet. You're already intimately familiar with strings as a data type in programming. The formal definition aligns perfectly with that concept.

A string (or word) over an alphabet $\Sigma$ is a finite sequence of symbols from $\Sigma$.

• Example: If $\Sigma =\{a,b\}$, then a, b, ab, baba, and aaabbb are all strings over $\Sigma$.
• The Empty String: A special, and very important, string is the empty string, which has zero symbols. It is denoted by $ϵ$ (epsilon) or sometimes $\lambda$ (lambda). The length of the empty string is 0.
• String Length: The length of a string $w$, denoted $|w|$, is the number of symbols in it. For example, if $w=ababa$, then $|w|=5$. For the empty string, $|ϵ|=0$.

To get a more dynamic and example-driven explanation of these concepts, the following video is quite helpful.

Sets of Strings

Using our alphabet $\Sigma$, we can define sets of strings of a specific length.

• ${\Sigma }^k$ is the set of all strings over $\Sigma$ of length exactly $k$.
• ${\Sigma }^0=\{ϵ\}$ (the set containing only the empty string).
• ${\Sigma }^1=\{a,b\}$ if $\Sigma =\{a,b\}$ (the set of all strings of length 1).
• ${\Sigma }^2=\{aa,ab,ba,bb\}$ if $\Sigma =\{a,b\}$.

The most important set of strings is the set of all possible strings of any finite length over an alphabet $\Sigma$. This is called the Kleene Star of $\Sigma$, denoted ${\Sigma }^{\ast }$. It is the universal set from which we will draw our languages.

A related concept is ${\Sigma }^{+}$ (pronounced "sigma plus"), which is the set of all non-empty strings.

Therefore, ${\Sigma }^{\ast }={\Sigma }^{+}\cup \{ϵ\}$.

The image below provides a great visual summary of these concepts.

3. Formal Languages: Sets of Strings

Now we arrive at the final and most crucial definition for this lesson. In the context of theory of computation, a "language" is not what we typically think of (like Python or English). Instead, it has a very simple and precise mathematical definition.

A language $L$ over an alphabet $\Sigma$ is any subset of ${\Sigma }^{\ast }$.
$L\subseteq {\Sigma }^{\ast }$

That's it. A formal language is simply a set of strings. The strings in the set are said to be "in the language," and the strings not in the set are "not in the language."

Examples of Languages:

Let $\Sigma =\{0,1\}$. The following are all languages over $\Sigma$:

• $L_1=\{w\in {\Sigma }^{\ast }\mid w\text{ has an even number of 0s}\}$.
  • Strings in $L_1$: $ϵ$, 1, 00, 1010, 111.
  • Strings not in $L_1$: 0, 10, 000.
• $L_2=\{0^n{1}^n\mid n\ge 0\}$. This is set-builder notation for "the set of strings consisting of $n$ zeros followed by $n$ ones, for any non-negative integer $n$".
  • Strings in $L_2$: $ϵ$ (for $n=0$), 01 (for $n=1$), 0011 (for $n=2$), etc.
  • Strings not in $L_2$: 0, 1, 010, 001.
• $L_3=\{0,1,00,11\}$. This is a finite language.
• The empty language, $L_4=\varnothing$. This language contains no strings.
• The language containing only the empty string, $L_5=\{ϵ\}$. Note that this is different from the empty language!

Your work in AI and development often involves defining or validating specific data formats. For instance, the set of all valid JSON objects is a language over the alphabet of ASCII characters. The set of all valid Bitcoin transaction scripts is a language. This course will give you the tools to reason about the complexity of recognizing such languages.

To solidify these definitions, the following reading provides the formal, set-theoretic definitions for strings and languages.

Conclusion

This lesson established the fundamental vocabulary for our study of computation. Let's recap the key takeaways:

• An alphabet ($\Sigma$) is a finite, non-empty set of symbols.
• A string is a finite sequence of symbols from an alphabet. The set of all possible strings over $\Sigma$ is denoted ${\Sigma }^{\ast }$.
• A formal language is any subset of ${\Sigma }^{\ast }$.

This simple, hierarchical structure—alphabets define strings, and sets of strings form languages—is the foundation upon which the entire field is built. A "computational problem" can be framed as a question of language membership: given a language $L$ and a string $w$, is $w$ in $L$? The rest of this course is about designing abstract machines (automata) that can answer this question for different kinds of languages and understanding the limits of what such machines can do.

In the next lesson, we will delve deeper into the properties of strings, exploring operations like concatenation and reversal. We will then use mathematical induction to prove some fundamental properties of these operations, giving you your first taste of the formal reasoning that is central to this field.