正则表达式

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

ε 是一个正则表达式，表示包含空字符串的语言。(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 多次应用任何规则，它们都是正则表达式。

一些正则表达式示例

正则表达式	正则集
(0 + 10*)	L = { 0, 1, 10, 100, 1000, 10000, … }
(010)	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)*	偶数长度的 a 和 b 字符串可以通过连接 aa、ab、ba 和 bb 的任意组合（包括空字符串）获得，所以 L = {aa, ab, ba, bb, aaab, aaba, …………..}

打印页面

广告