哈工大形式语言slide 5-2015.pdf

Regular Expression 1. Definition 2. Designing 3. Equivalence with FA 2 Operation of Languages L={ 0,11 }, M ={  , 001 }  Union LM={ 0, 11 ,  , 001 }  Concatenation LM={ 0, 11, 0001 , 11001 } ML={ 0, 11, 0010, 00111 } 3 Operation of Languages L={ 0,11 }  Star ( Closure , Kleene Closure ) 0 1 2 L ={}, L ={0,11}, L ={00,011,110,1111} L3 ={000,0011,0110,1100,01111,11011,11110,111111} *  i L i 0 L *  = ? 4 Arithmetical Expression 0, 1+2, 3(5-2), (56-7)2 ,   Formal definition  Inductive definition  Any number is a arithmetical expression  If a and b are arithmetical expressions , then so is a+b,a-b,ab, ab,an, (a) . 5 Building Regular Expressions BASIS 1.  is a regular expression, denoting the languages {}. 2.  is a regular expression, denoting the languages  . 3. For each a in  , a is a regular expression and denotes the language {a }. 6 Building Regular Expressions INDUCTION 1. If E and F are regular expressions, denoting the language L(E ) and L(F ), then E +F , EF and E * are regular expressions that denote the languages L(E ) * L(F ), L(E )L(F ) and (L(E )) . 2. If E is a RE then so is (E ) . 7 Example 5.1 What is the language defined by r