Regular Languages

Definition 2.1

An alphabet, denoted by , is a set of symbols. A string or word is a sequence a 1 a 2 a 3 a 4 ... a n where a i

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

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

Definition 2.2

Let * denote the set of all strings of including the empty string.

Define the binary operation called concatenation on * as follows:

If a 1 a 2 a 3 a 4 ... a n and b 1 b 2 b 3 b 4 ... b n * then

a 1 a 2 a 3 a 4 ... a n   ○   b 1 b 2 b 3 b 4 ... b n = a 1 a 2 a 3 a 4 ... a n b 1 b 2 b 3 b 4 ... b n

Definition 2.3

Let B be a subset of * then B* is the set of all strings or words formed by concatenating words from B together with the empty string, i.e.
B* ={ w 1 w 2 ... w n : w i B } { λ }

If denotes the empty set then *={λ}

The symbol  * is called the Kleene star

Definition 2.4

Let Σ* denote the set of all strings of Σ including the empty string. A subset L of Σ* is called a language.

Definition 2.5

Let Σ be an alphabet. The class of regular expressions R over math>Σ is defined by the following rules using Σ and the symbols &empty,&lambda, *,,(,and).