常用表达

正则表达式可以递归定义如下 -

  • ε是正则表达式，表示包含空字符串的语言。(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(XY) = L(X) 。左(Y)

    • R*是对应于语言L(R*)的正则表达式，其中L(R*) = (L(R))*

  • 如果我们多次应用任何规则（从 1 到 5），它们就是正则表达式。

一些正则表达式的例子

常用表达 常规套装
(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, aabb, …………..}
(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, ………….. }