An alphabet, denoted by , is a set of symbols. A string or word is a sequence
Thus if , 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
denote the set of all strings of
including the empty string.
Define the binary operation ○ called concatenation on
Let B be a subset of
is the set of all strings or words formed by concatenating words from B together with the empty string, i.e.
(i) The symbol is a regular expressions and for every
, the symbol a is a regualar expression.