DESKTOP

# Algorithms for Compiler Design: REGULAR SETS AND REGULAR EXPRESSIONS

7/24/2010 7:58:03 PM
##### 2.8 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. 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. var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>");
 Other

 Top 10
 REVIEW
- First look: Apple Watch

- 3 Tips for Maintaining Your Cell Phone Battery (part 1)

- 3 Tips for Maintaining Your Cell Phone Battery (part 2)