NANJING UNIVERSITY Regular Expressions Definitions Equivalence to Finite Automata .1
1 Regular Expressions Definitions Equivalence to Finite Automata
效绵鼎 RE's:Introduction Regular expressions describe languages by an algebra. They describe exactly the regular languages. If E is a regular expression,then L(E)is the language it defines. We'll describe RE's and their languages recursively. 2
2 RE’s: Introduction ◼ Regular expressions describe languages by an algebra. ◼ They describe exactly the regular languages. ◼ If E is a regular expression, then L(E) is the language it defines. ◼ We’ll describe RE’s and their languages recursively
效绵鼎 Operations on Languages RE's use three operations:union,concatenation, and Kleene star. The union of languages is the usual thing,since languages are sets. ■Example:{01,111,10{00,01}={01,111,10,00} 3
3 Operations on Languages ◼ RE’s use three operations: union, concatenation, and Kleene star. ◼ The union of languages is the usual thing, since languages are sets. ◼ Example: {01,111,10}{00, 01} = {01,111,10,00}
效绵鼎 Concatenation The concatenation of languages L and M is denoted LM. It contains every string wx such that w is in L and x is in M. Example:{01,111,10}{00,01}={0100,0101, 11100,11101,1000,1001}. 4
4 Concatenation ◼ The concatenation of languages L and M is denoted LM. ◼ It contains every string wx such that w is in L and x is in M. ◼ Example: {01,111,10}{00, 01} = {0100, 0101, 11100, 11101, 1000, 1001}
效绵鼎 Kleene Star If L is a language,then L*,the Kleene star or just “star,”is the set of strings formed by concatenating zero or more strings from L,in any order. ■ L*=LOLLOLLLO... Example:{0,10}*={e,0,10,00,010,100, 1010,..} .5
5 Kleene Star ◼ If L is a language, then L*, the Kleene star or just “star,” is the set of strings formed by concatenating zero or more strings from L, in any order. ◼ L* = {ε} L LL LLL … ◼ Example: {0,10}* = {ε, 0, 10, 00, 010, 100, 1010,…}
效绵鼎 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