Automata Theory 简明教程

Regular Expressions

A Regular Expression 可按照以下方式递归定义 −

  1. ε 是表示包含空字符串的语义的正则表达式。 (L (ε) = {ε})

  2. φ 是表示空语义的正则表达式。 (L (φ) = { })

  3. x 是正则表达式，其中 L = {x}

  4. 如果 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 的正则表达式) where *L(R ) = (L®)*

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

Some RE Examples

Regular Expressions

Regular Set

(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)*

偶数长度的 a 和 b 的字符串可以通过连接包括空串在内的 aa、ab、ba 和 bb 的任意组合获得，所以 L = {aa, ab, ba, bb, aaab, aaba, …………..}