Defining Languages

Terminology §

• A symbol is the smallest unit in a language.
• An alphabet is the set of all symbols available in the language.
• A string is a series of 0 or more symbols from the alphabet.
• The empty word (denoted by $ϵ$) is a string containing no letters.
• A language is a set of words.
• Concatenation (denoted as $a+b$)is an operation which takes two strings and returns the first followed by the second.
  • Concatenation can be denoted as a power - $s^n$ is the string $s$ concatenated with itself $n$ times.

Operations on Languages §

As languages are sets, we can apply some set operations to them, including:

• Union (${\mathcal{L}}_1\cup {\mathcal{L}}_2$),
• Intersection (${\mathcal{L}}_1\cap {\mathcal{L}}_2$),
• Complement (${\mathcal{L}}_1\backslash {\mathcal{L}}_2$) We can also apply some other operations:
• Concatenation - ${\mathcal{L}}_1\cdot {\mathcal{L}}_2=\{s\cdot t|s\in {\mathcal{L}}_1,t\in {\mathcal{L}}_2\}$,
• N-ary concatenation- ${\mathcal{L}}^n=\{s_1\cdot ...\cdot s_n|s_i\in \mathcal{L}\forall 1\le i\le n\}$.

Types of languages §

Regular Languages §

Regular Languages can be described by Regular Expressions. Given regular languages ${\mathcal{L}}_1$ and ${\mathcal{L}}_2$, the following are also regular languages:

• ${\mathcal{L}}_1\cup {\mathcal{L}}_2$,
• ${\mathcal{L}}_1\cdot {\mathcal{L}}_2$,
• ${\mathcal{L}}_1^n$,
• ${\mathcal{L}}_1\ast$.