Regular Expression
2
1. Definition 2. Designing 3. Equivalence with FAArithmetical 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
n so is a+b,a-b,a?b, a?b,a, (a) .
3
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 }.
4
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 ) .
5
形式语言与自动机slide 5-2019
