Formal Languages

Definition

Let $\Sigma $ be a finite set (alphabet). A formal language (or language) is a subset of finite-length strings of elements of $\Sigma $.

Examples

Let $\Sigma = \set{0,1}$. Then $\varnothing$ is a language, as are the sets $\set{0, 1}$ and $\set{01, 001, 111, 1101010}$.

Notation

We denote the finite strings of $\Sigma $ by $\str(\Sigma )$. Other common notation is $\Sigma ^*$, which we avoid in these sheets for its collision with adjoints.