正则表达式
2025-07-31 00:38:11 南非世界杯排名正则表达式可以用形式化语言理论的方式来表达。正则表达式由常量和算子组成，它们分别表示字符串的集合和在这些集合上的运算。给定有限字母表Σ定义了下列常量：
空集
∅
{\displaystyle \varnothing }
表示集合
∅
{\displaystyle \varnothing }
。
空串
ε
{\displaystyle \varepsilon }
表示仅包含一个“不含任何字符、长度为0的字符串”的集合。
文字字符（英语：String literal）
a
∈
Σ
{\displaystyle a\in \Sigma }
表示仅包含一个元素
a
{\displaystyle a}
的集合
{
a
}
{\displaystyle \{a\}}
。
定义了下列运算：
串接
R
S
{\displaystyle RS}
表示集合
{
α
β
∣
α
∈
R
,
β
∈
S
}
{\displaystyle \{\alpha \beta \mid \alpha \in R,\beta \in S\}}
，这里的
α
β
{\displaystyle \alpha \beta }
表示将
α
{\displaystyle \alpha }
和
β
{\displaystyle \beta }
两个字符串按顺序连接。例如：
{
a
b
,
c
}
{
d
,
e
f
}
=
{
a
b
d
,
a
b
e
f
,
c
d
,
c
e
f
}
{\displaystyle \{ab,c\}\{d,ef\}=\{abd,abef,cd,cef\}}
。
选择
R
|
S
{\displaystyle R|S}
表示
R
{\displaystyle R}
和
S
{\displaystyle S}
的并集。例如：
{
a
b
,
c
}
|
{
a
b
,
d
,
e
f
}
=
{
a
b
,
c
,
d
,
e
f
}
{\displaystyle \{ab,c\}|\{ab,d,ef\}=\{ab,c,d,ef\}}
。
克莱尼(Kleene)星号
R
∗
{\displaystyle R^{*}}
表示包含
ε
{\displaystyle \varepsilon }
且在字符串串接运算下闭合的
R
{\displaystyle R}
的最小超集。这是可以通过
R
{\displaystyle R}
中零或有限个字符串的串接得到所有字符串的集合。例如：
{
a
b
,
c
}
∗
=
{
ε
,
a
b
,
c
,
a
b
a
b
,
a
b
c
,
c
a
b
,
c
c
,
a
b
a
b
a
b
,
⋯
}
{\displaystyle \{ab,c\}^{*}=\{\varepsilon ,ab,c,abab,abc,cab,cc,ababab,\cdots \}}
。
上述常量和算子形成了克莱尼代数。
很多课本使用对选择使用符号
∪
{\displaystyle \cup }
、
+
{\displaystyle +}
或
∨
{\displaystyle \vee }
替代竖线。
为了避免括号，假定Kleene星号有最高优先级，接着是串接，接着是并集。如果没有歧义则可以省略括号。例如：(ab)c可以写为abc，而a|(b(c*))可以写为a|bc*。
例子：
a|b*表示
{
ε
,
a
,
b
,
b
b
,
b
b
b
,
⋯
}
{\displaystyle \{\varepsilon ,a,b,bb,bbb,\cdots \}}
。
(a|b)*表示包括空串和任意数目个a或b字符组成的所有字符串的集合：
{
ε
,
a
,
b
,
a
a
,
a
b
,
b
a
,
b
b
,
a
a
a
⋯
}
{\displaystyle \{\varepsilon ,a,b,aa,ab,ba,bb,aaa\cdots \}}
。
ab*(c|ε)表示开始于一个a接着零或多个b和最后一个可选的c组成的字符串的集合：
{
a
,
a
c
,
a
b
,
a
b
c
,
a
b
b
,
a
b
b
c
⋯
}
{\displaystyle \{a,ac,ab,abc,abb,abbc\cdots \}}
。
为了使表达式更简洁，正则表达式也定义了?和+；aa*等于a+，表示a出现至少一次；而(a|ε)等于a?，表示a出现1次或不出现。有的定义中增加了补算子
∼
{\displaystyle \sim }
；
∼
R
{\displaystyle \sim R}
表示在
Σ
∗
{\displaystyle \Sigma ^{*}}
上但不在
R
{\displaystyle R}
中的所有字符串的集合。补算子在理论上并非必要，因为它可以使用其他算子来表达，但它可以使一些表达式变得更加简洁。
这种意义上的正则表达式可以表达正则语言，是可被有限状态自动机精确接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述，而要求的正则表达式的长度只线性的增长。
正则表达式对应于乔姆斯基层级的类型-3文法。但通常编程语言或其相关库（例如PCRE）中实现的正则表达式的表达能力是乔姆斯基层级中类型-3文法的超集[来源请求]。在另一方面，在正则表达式和不导致这种大小上的爆炸的非确定有限状态自动机（NFA）之间有简单的映射；为此NFA经常被用作正则表达式的替表示式。
这种形式化中存在着冗余，典型的体现是存在不同的正则表达式可以表达同样的语言。有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等，即简约每个表达式到极小确定有限自动机，确定它们是否同构（等价）。这种冗余可以消减到什么程度？我们可以找到仍有完全表达力的正则表达式的有趣的子集吗？这提出了一个令人惊奇的困难问题。Kleene星号和并集明显是需要的，但是我们或许可以限制它们的使用。由于正则表达式如此简单，没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了星号高度问题（英语：Star height problem）。最近Dexter Kozen用克莱尼代数公理化了正则表达式。[来源请求]
很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。[来源请求]