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.
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 & pound ; is a regular expression | { a } |
|
r 1 + r 2 or r 1 r 2 is a regular expression, | R 1 ˆ R 2 (Where R 1 and R 2 are regular sets corresponding to r 1 and r 2 , respectively) | |
r 1 . r 2 is a regular expression, | R 1 . R 2 (Where R 1 and R 2 are regular sets corresponding to r 1 and r 2 , respectively) | |
r * is a regular expression, | R * (where R is a regular set corresponding to 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 2.25.
Since closure is required next , we construct the automata for ( a + b )*, using the automata for a + b , as shown in Figure 2.26.
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 2.27.
Next we construct the automata for a .( a + b )*. b , as shown in Figure 2.28.
Finally, we construct the automata for a .( a + b )*. b . b (Figure 2.29).
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.