正则表达式

• 正则表达式是定义字符串的一系列模式。它用于表示常规语言。
• 它还用于匹配字符串中的字符组合。字符串搜索算法使用此模式来查找字符串操作。
• 在正则表达式中, x *表示零个或多个x出现。它可以生成{e, x, xx, xxx, xxxx, …..}
• 在正则表达式中, x +表示x的一个或多个出现。它可以生成{x, xx, xxx, xxxx, …..}

常规语言操作

常规语言的各种操作是：

联合：如果L和M是两种常规语言, 则它们的联合L U M也是联合。

L U M = {s | s is in L or s is in M}

交集：如果L和M是两种常规语言, 则它们的交集也是交集。

L ⋂ M = {st | s is in L and t is in M}

方括号闭合：如果L是常规语言, 则其方括号闭合L1 *也将是常规语言。

L* = Zero or more occurrence of language L.

例

编写该语言的正则表达式：

L = {abn w:n ≥ 3, w ∈ (a, b)+}

解：

语言字符串L以“ a”开头, 后接至少三个b。它包含至少一个字符串“ a”或一个“ b”, 例如abbba, abbbbbba, abbbbbbbb, abbbb ….. a

因此正则表达式为：

r= ab3b* (a+b)+

这里+是一个正闭包, 即（a + b）+ =（a + b）*-∈