Algorithms for Compiler Design: REGULAR SETS AND REGULAR EXPRESSIONS

1 Regular Sets

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.

Regular expression	Regular Set	Finite automata
φ	{ }
∈	{ ∈ }
Every a in Σ is a regular expression	{a}
r1 + r2 or r1 | r2 is a regular expression,	R1 ∪ R2 (Where R1 and R2 are regular sets corresponding to r1 and r2, respectively)	where N1 is a finite automata accepting R1, and N2 is a finite automata accepting R2
r1 . r2 is a regular expression,	R1.R2 (Where R1 and R2 are regular sets corresponding to r1 and r2, respectively)	where N1 is a finite automata accepting R1, and N2 is finite automata accepting R2
r* is a regular expression,	R* (where R is a regular set corresponding to r)	where N is a finite automata accepting R.

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.

Figure 1: Transition diagram for (a + b).

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

Figure 2: Transition diagram for (a + b)*.

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.

Figure 3: Transition diagram for a. (a + b)*.

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

Figure 4: Automata for a.(a + b)* .b.

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

Figure 5: Automata for a.(a + b)*.b.b.

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.