# Regular Languages



## Definition 2.1

An alphabet, denoted by $\sum$ , is a set of symbols. A string or word is a sequence ${a}_{1}{a}_{2}{a}_{3}{a}_{4}\mathrm{...}{a}_{n}$ where ${a}_{i}\in \sum$

Thus if $\sum =\left\{a,b\right\}$, then ab, a, abba, bbbbbb, baaaaaaaaaaa, would all be strings of symbols of $\sum$.

In addition we include an empty string denoted by $\lambda$ which has no symbols in it .

## Definition 2.2

Let ${\sum }^{*}$ denote the set of all strings of $\sum$ including the empty string.

Define the binary operation called concatenation on ${\sum }^{*}$ as follows:

If ${a}_{1}{a}_{2}{a}_{3}{a}_{4}\mathrm{...}{a}_{n}$ and ${b}_{1}{b}_{2}{b}_{3}{b}_{4}\mathrm{...}{b}_{n}\in {\sum }^{*}$ then

## Definition 2.3

Let B be a subset of ${\sum }^{*}$ then B* is the set of all strings or words formed by concatenating words from B together with the empty string, i.e.
${B}^{*}=\left\{{w}_{1}{w}_{2}\mathrm{...}{w}_{n}:{w}_{i}\in B\right\}\cup \left\{\lambda \right\}$

If $\varnothing$ denotes the empty set then ${\varnothing }^{*}=\left\{\lambda \right\}$

The symbol is called the Kleene star

## Definition 2.4

Let ${\Sigma }^{*}$ denote the set of all strings of $\Sigma$ including the empty string. A subset $L$ of ${\Sigma }^{*}$ is called a language.

## Definition 2.5

Let $\Sigma$ be an alphabet. The class of regular expressions $R$ over math>Σ is defined by the following rules using $\Sigma$ and the symbols .

• (i) The symbol $\varnothing$ is a regular expressions and for every $a\in \Sigma$, the symbol a is a regualar expression.