正则表达式
正则表达式可以递归定义如下 −
ε 是一个正则表达式，表示包含空字符串的语言。(L (ε) = {ε})
φ 是一个正则表达式，表示空语言。 (L (φ) = { })
x 是一个正则表达式，其中 L = {x
如果 X 是一个表示语言 L(X) 的正则表达式，而 Y 是一个表示语言 L(Y) 的正则表达式，则
X + Y 是一个对应于语言 L(X) ∪ L(Y) 的正则表达式，其中 L(X+Y) = L(X) ∪ L(Y)。
X . Y 是一个对应于语言 L(X) . L(Y) 的正则表达式，其中 L(X.Y) = L(X)。 L(Y)
R* 是对应于语言 L(R*) 的正则表达式，其中 L(R*) = (L(R))*
如果我们多次应用 1 到 5 中的任何规则，它们就是正则表达式。
一些 RE 示例
| 正则表达式 | 正则集 |
|---|---|
| (0 + 10*) | L = { 0, 1, 10, 100, 1000, 10000, … > |
| (0*10*) | L = {1, 01, 10, 010, 0010, …> |
| (0 + ε)(1 + ε) | L = {ε, 0, 1, 01> |
| (a+b)* | 任意长度的 a 和 b 字符串集（包括空字符串）。所以 L = { ε, a, b, aa , ab , bb , ba, aaa…….> |
| (a+b)*abb | 以字符串 abb 结尾的 a 和 b 字符串集合。所以 L = {abb, aabb, babb, aaabb, ababb, …………..> |
| (11)* | 由偶数个 1 组成的集合（包括空字符串），所以 L= {ε, 11, 1111, 111111, ……….> |
| (aa)*(bb)*b | 由偶数个 a 和奇数个 b 组成的字符串集合，所以 L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, …………..> |
| (aa + ab + ba + bb)* | 可以通过连接字符串 aa、ab、ba 和 bb 的任意组合（包括 null）来获得长度为偶数的 a 和 b 的字符串，因此 L = {aa, ab, ba, bb, aaab, aaba, …………..> |
