Formal Languages

Introduction

Doing mathematics requires the use of language for writing down formulas and expressions. However, the languages we use to communicate on a daily basis are not really suitable for this purpose because they are overly complex and inconsistent due to the large number of rules and exceptions they have.

This is why mathematicians have devised languages, known as formal languages, which are simple and without exceptions.

Formal Languages

Definition: Alphabets and Symbols

An alphabet is a non-empty set whose elements we call symbols or letters.

NOTATION

Alphabets are commonly denoted by the uppercase Greek letter sigma ($\Sigma$).

Example

As per the definition, any non-empty set can be an alphabet. This includes the uppercase English alphabet $\{A,B,\dots ,Y,Z\}$, the lowercase Greek alphabet $\{\alpha ,\beta ,\dots ,\omega \}$, the natural numbers $\mathbb{N}$, the set $\{\circ ,+,-,△\}$ and so on.

Definition: Expression

Let $\Sigma$ be an alphabet.

An expression (or string or word) over $\Sigma$ is any $n$-tuple whose elements are symbols from $\Sigma$.

NOTATION

Expressions are usually written by listing their symbols directly, instead of placing them between parentheses in a comma-separated list, as is usually the case with tuples. For example, the expression $(a,2,s,s,1,w)$ is written as $a2ss1w$.

Notation: Kleene Star

The set of all finite-length expressions over a given alphabet $\Sigma$ is denoted by ${\Sigma }^{\ast }$.

Example: Expressions

If $\Sigma =\{a,b,1,+,-\}$, then some expressions over $\Sigma$ are $a$, $1b$, $aba$, $11abb$, $1b+-a$, etc.

Definition: Formal Language

A formal language over an alphabet $\Sigma$ is any subset of the set of all finite-length expressions ${\Sigma }^{\ast }$ over $\Sigma$.

Notation

Formal languages are commonly denoted by $\mathcal{L}$.