A regular set is a set of strings for which there exists some finite automata that accepts that set. That is, if *R* is a regular set, then *R* = *L*(*M*) for some finite automata *M*. Similarly, if *M* is a finite automata, then *L*(*M*) is always a regular set.

###
2 Regular Expression

A regular expression is a notation to specify a regular set. Hence, for every regular expression, there exists a finite automata that accepts the language specified by the regular expression. Similarly, for every finite automata *M*, there exists a regular expression notation specifying *L*(*M*). Regular expressions and the regular sets they specify are shown in the following table.

Hence, we only have three regular-expression operators: | or + to denote union operations,. for concatenation operations, and * for closure operations. The precedence of the operators in the decreasing order is: *, followed by., followed by | . For example, consider the following regular expression:

To construct a finite automata for this regular expression, we proceed as follows: the basic regular expressions involved are *a* and *b*, and we start with automata for *a* and automata for *b*. Since brackets are evaluated first, we initially construct the automata for *a* + *b* using the automata for *a* and the automata for *b*, as shown in Figure 1.

Since closure is required next, we construct the automata for (*a* + *b*)*, using the automata for *a* + *b*, as shown in Figure 2.

The next step is concatenation. We construct the automata for *a*. (*a* + *b*)* using the automata for (*a* + *b*)* and *a*, as shown in Figure 3.

Next we construct the automata for *a*.(*a* + *b*)*.*b*, as shown in Figure 4.

Finally, we construct the automata for *a*.(*a* + *b*)*.*b*.*b* (Figure 5).

This is an NFA with ∈-moves, but an algorithm exists to transform the NFA to a DFA. So, we can obtain a DFA from this NFA.