效绵鼎 RE's:Definition Basis 1:If a is any symbol,then a is a RE,and L(a) ={a}. o Note:{a}is the language containing one string,and that string is of length 1. Basis 2:E is a RE,and L(E)=e. Basis3:☑is a RE,andL(☑)=☑. 6
6 RE’s: Definition ◼ Basis 1: If a is any symbol, then a is a RE, and L(a) = {a}. Note: {a} is the language containing one string, and that string is of length 1. ◼ Basis 2: ε is a RE, and L(ε) = {ε}. ◼ Basis 3: ∅ is a RE, and L(∅) = ∅
效绵鼎 RE's:Definition-(2) Induction 1:If E and E2 are regular expressions, then E+E2 is a regular expression,and L(E+E2)= L(EOLE2). Induction 2:If E and E2 are regular expressions, then E E2 is a regular expression,and L(E E2)= L(E1)L(E2). Induction 3:If E is a RE,then E*is a RE,and L(E*)=(L(E)* 7
7 RE’s: Definition – (2) ◼ Induction 1: If E1 and E2 are regular expressions, then E1+E2 is a regular expression, and L(E1+E2 ) = L(E1 )L(E2 ). ◼ Induction 2: If E1 and E2 are regular expressions, then E1E2 is a regular expression, and L(E1E2 ) = L(E1 )L(E2 ). ◼ Induction 3: If E is a RE, then E* is a RE, and L(E*) = (L(E))*
效缥县 Precedence of Operators Parentheses may be used wherever needed to influence the grouping of operators. Order of precedence is (highest),then concatenation,then +(lowest) 8
8 Precedence of Operators ◼ Parentheses may be used wherever needed to influence the grouping of operators. ◼ Order of precedence is * (highest), then concatenation, then + (lowest)
效绵鼎 Examples:RE's L(01)={01}. L(01+0)={01,0}. L(0(1+0)={01,00}. 0 Note order of precedence of operators. ■L(0*)={e,0,00,000,.}. ■ L((0+10)*(E+1))=all strings of0's and 1's without two consecutive 1 s. 9
9 Examples: RE’s ◼ L(01) = {01}. ◼ L(01+0) = {01, 0}. ◼ L(0(1+0)) = {01, 00}. Note order of precedence of operators. ◼ L(0*) = {ε, 0, 00, 000,… }. ◼ L((0+10)*(ε+1)) = all strings of 0’s and 1’s without two consecutive 1’s
效绵鼎 Equivalence of RE's and Finite Automata We need to show that for every RE,there is a finite automaton that accepts the same language. o Pick the most powerful automaton type:the E-NFA. And we need to show that for every finite automaton,there is a RE defining its language. o Pick the most restrictive type:the DFA .10
10 Equivalence of RE’s and Finite Automata ◼ We need to show that for every RE, there is a finite automaton that accepts the same language. Pick the most powerful automaton type: the ε-NFA. ◼ And we need to show that for every finite automaton, there is a RE defining its language. Pick the most restrictive type: the DFA