正则表达式

• 由有限自动机接受的语言可以用称为正则表达式的简单表达式轻松描述。这是表示任何语言的最有效方法。
• 某些正则表达式接受的语言被称为正则语言。
• 正则表达式也可以被描述为定义字符串的一系列模式。
• 正则表达式用于匹配字符串中的字符组合。字符串搜索算法使用此模式对字符串执行操作。

例如

在正则表达式中，x* 表示 x 的零个或多个出现。它可以生成 {e, x, xx, xxx, xxxx, .....}

在正则表达式中，x⁺ 表示 x 的一个或多个出现。 它可以生成 {x, xx, xxx, xxxx, .....}

对正则语言的操作

对正则语言的各种操作是

并集：如果 L 和 M 是两种正则语言，那么它们的并集 L U M 也是一个并集。

交集：如果 L 和 M 是两种正则语言，那么它们的交集也是一个交集。

克林闭包：如果 L 是一种正则语言，那么它的克林闭包 L1* 也将是一种正则语言。

示例 1

为接受集合 ∑ = {a} 上所有 a 组合的语言编写正则表达式

解决方案

所有 a 的组合意味着 a 可以为零个、单个、双个等等。如果 a 出现零次，这意味着一个空字符串。也就是说，我们期望集合为 {ε, a, aa, aaa, ....}。 因此，我们为此提供一个正则表达式：

即 a 的克林闭包。

示例 2

为接受集合 ∑ = {a} 上所有 a 的组合（空字符串除外）的语言编写正则表达式

解决方案

必须为该语言构建正则表达式

该集合表明不存在空字符串。 因此我们可以将正则表达式表示为

R = a+

示例 3

为接受包含任意数量的 a 和 b 的所有字符串的语言编写正则表达式。

解决方案

正则表达式将是

这将给出集合 L = {ε, a, aa, b, bb, ab, ba, aba, bab, .....}，即 a 和 b 的任何组合。

(a + b)* 显示了与 a 和 b 的任何组合，甚至是空字符串。