1.2 Regular Expression

正则表达式是一种形式语言，formal language，被广泛使用的最弱的形式语言（the weakest formal language）；

Atomic RE:

• Single Character: L('c') = ["c"];
• Epsilon: $L(\varepsilon)$ = [""];
• Concentration: L(AB) = $\{ab | a\in L(A),b\in L(B)\}$；
• Union: L(A | B) = $\{s|s\in L(A)\text{ or }s\in L(B)\}$；
• Repitation: $L(A^*)=L(\varepsilon)\space|\space L(A)\space|\space L(AA)\space|\space\cdots$；