Languages

Basic Terminology

Alphabet - a finite set (of symbols/letters). Examples include:

• $\{0,1\}$
• $\{a,b,c,\dots ,z\}$

We denote an alphabet by $\Sigma$
In this module, alphabets are finite

String (word) - a finite sequence of symbols. Examples include:

• $hello$ for $\Sigma =\{a,b,c,\dots ,z\}$

${\Sigma }^{\ast }$ means “all strings”.
$ϵ$ means “empty string”.
${\Sigma }^{+}$ means “all non-empty strings” i.e. ${\Sigma }^{+}={\Sigma }^{\ast }\setminus \{ϵ\}$

Kleene Star

The asterisk in ${\Sigma }^{\ast }$ is called the “Kleene Star”.

It is defined by $A^{\ast }=\{x_1{x}_2\dots x_k|k\ge 0,x_i\in A\}.$

Example 1: $\{0{\}}^{\ast }=\{ϵ,0,00,000,\dots \}.$
Example 2: $\{0,1{\}}^{\ast }=\{ϵ,0,1,00,01,10,11,\dots \}.$

Language - a subset of all strings. $L\subseteq {\Sigma }^{\ast }$