自动机正则表达式

2022-04-15 自动机教程

本文概述

正则表达式操作

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

例如：
在正则表达式中，x *表示x出现零次或多次。它可以生成{e，x，xx，xxx，xxxx，… ..}
在正则表达式中，x表示x的一个或多个出现。它可以生成{x，xx，xxx，xxxx，… ..}
正则表达式操作正则表达式的各种操作是：
联合：如果L和M是两种正则表达式，则它们的联合L U M也是联合。

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

交集：如果L和M是两种正则表达式，则它们的交集也是交集。

1. L ? M = {st | s is in L and t is in M}

Kleen闭包：如果L是正则表达式，则其Kleen闭包L1 *也将是正则表达式。

1. L* = Zero or more occurrence of language L.

范例1：
在集合∑ = {a}上为接受a的所有组合的语言编写正则表达式
解：
a的所有组合均意味着a可以为零，单个，双精度等。如果a出现零次，则表示一个空字符串。那就是我们期望{ε，a，aa，aaa，… .}的集合。因此，我们为此给出一个正则表达式：

R = a*

那是克莱恩的闭包。
范例2：
在集合∑ = {a}上为接受a的所有组合（除了空字符串）编写语言的正则表达式
解：
必须为该语言构建正则表达式

L = {a, aa, aaa, ....}

该集合指示没有空字符串。因此我们可以将正则表达式表示为：

R = a+

范例3：
为该语言编写正则表达式，以接受包含任意数量的a和b的所有字符串。
解：
正则表达式为：

r.e. = (a + b)*

【自动机正则表达式】这将使集合为L = {ε，a，aa，b，bb，ab，ba，aba，bab，… ..}，a和b的任意组合。
（a b）*显示带有a和b的任何组合，甚至是一个空字符串。

推荐阅读

上一篇：从NFA到DFA的自动机转换

下一篇：自动机正则表达式的例子