正则表达式

一种定义语言的新方法

  之前提到过许多种定义一个语言的方法,诸如:
1. \mathcal{L_1}=\lbrace x^n\ for\ n=1,2,3...\rbrace
2. \mathcal{L_2}=\lbrace x^n\ for\ n=1,3,5...\rbrace
3. \mathcal{L_3}=\lbrace x^n\ for\ n=1,4,9,16...\rbrace

这些定义中的共同点是我们可以轻松地发现蕴含在1,2,31,3,5或者1,4,9,16中的规律,但是如果对于类似1,9,12,28这种,我们就很难通过简单的定义前几个n的值来明确该数列的含义,因此我们需要一种比...更加精确地表示方法,考虑之前提到过的Kleene闭包,我们可以将语言\mathcal{L_4}=\lbrace \varLambda,x,xx,xxx,xxxx...\rbrace表示为集合\mathcal{S}=\lbrace x\rbrace上面的闭包\mathcal{L_4}=\mathcal{S}^\ast,这种表达方法可以进一步缩写成\mathcal{L_4}=\lbrace x\rbrace^\ast,此时,我们可以让这里的星号可以直接作用在一个单独的字符而非一个集合上:

\boldsymbol{x}^\ast

这代表着一个由\boldsymbol{x}重复0次或多次构成的字符串(在这里使用粗体和单独的字符x区分开来),也即:

\begin{aligned}
\boldsymbol{x}^\ast&=\varLambda/x/x^2/x^3...\\
&=x^n\ for\ n=0,1,2,3,4...
\end{aligned}

我们使用language(\boldsymbol{\footnotesize \varGamma})来表示被\footnotesize \varGamma所表示的语言,这里的\scriptstyle *虽然看上去和对集合的闭包运算颇为相似,但实际上它表达的意思是把在它之前之前的字符重复0次或多次,现在我们可以用如下的方法重新定义一遍\mathcal{L_4}了:

\mathcal{L_4}=language(\boldsymbol{x}^\ast)

注意不要把\boldsymbol{x}^\ast\mathcal{L_4}弄混,前者是一个用于定义语言的表达式,而后者是我们给这个语言取的一个名字。了解了这点之后,我们也可以用这种方法重新定义\varSigma=\lbrace a,b\rbrace上面的语言\mathcal{L}=\lbrace a,ab,abb,abbb,abbbb...\rbrace

\mathcal{L}=language(a\boldsymbol{b}^\ast)

在这里虽然ab一起出现,但是\scriptstyle *仅仅对b有效,如果想要对ab都有效,则需要写成\boldsymbol{(ab)}^\ast,这其中括号并不在子母表中,仅仅是用于指明ab被对待为一个整体对应的字符串为\boldsymbol{(ab)}^\ast=\varLambda/ab/abab/ababab...
类比之前提到过的\mathcal{S}^+,如果我们想让\boldsymbol{x}^*包含至少一个\boldsymbol{x},那么我们可以使用记号\scriptstyle +来定义,也即:

\begin{aligned}
\mathcal{L_1}&=language(\boldsymbol{xx}^\ast) \\
&=language(\boldsymbol{x}^+)
\end{aligned}

  定义xy是两串字符串,定义x+y的意义为"要么x,要么y"

形式化的定义

  上文中所描述的定义方式叫做正则表达式(Regular Expression),由正则表达式定义的语言叫做正则语言(Regular Language)

定义

DEFINITION
定义字母表\varSigma,正则表达式中允许出现的所有子串可以包含\varSigma中的元素,\boldsymbol{\varLambda}\scriptstyle *以及\scriptstyle +
正则表达式可以由一下规则定义:
1. 正则表达式可以包含任意\varSigma中的字母,\boldsymbol{\Lambda}(加粗的)本身就是一个正则表达式,用于表达空字符串\varLambda
2. 如果\footnotesize \varGamma_1\footnotesize \varGamma_2都是正则表达式,则以下也都是正则表达式:
3. 正则表达式仅包含能从1和2中推导出的元素
* (\footnotesize \varGamma_1)
* \footnotesize \varGamma_1\footnotesize \varGamma_2
* \footnotesize \varGamma_1+\footnotesize \varGamma_2
* \footnotesize \varGamma_1^\ast

注意此处没有定义\footnotesize \varGamma_1^+,因为\footnotesize \varGamma_1^+=\footnotesize \varGamma_1\footnotesize \varGamma_1^\ast(这里同样涉及到一个有趣的细节,也就是正则表达式是一个用于定义其他语言的语言)。
我们用加粗的\boldsymbol{\phi}来表示定义了语言\phi的正则表达式。对于任何正则表达式\footnotesize \varGamma

\footnotesize \varGamma+\boldsymbol{\phi}=\footnotesize \varGamma\\
\boldsymbol{\phi}\footnotesize \varGamma=\boldsymbol{\phi}\\
\boldsymbol{\Lambda}\footnotesize \varGamma=\footnotesize \varGamma

同时要注意,应当避免使用\boldsymbol{\phi}^\ast,因为他是无意义的
对于正则表达式\footnotesize \varGamma_1\footnotesize \varGamma_2,如果他们描述的是同一种语言,那么可以写作:

\footnotesize \varGamma_1=\footnotesize \varGamma_2

对于一个包含了\varLambda的语言,用于定义这个语言的正则表达式必须包含\boldsymbol{\Lambda},比如,对于\varSigma=\lbrace a,b\rbrace上的语言\mathcal{L}=\lbrace \varLambda,a,aa,bbb\rbrace,使用正则表达式时需要定义为\mathcal{L}=\lbrace \boldsymbol{\Lambda}+a+aa+bbb\rbrace

集合的乘积

DEFINITION
\mathcal{S}\mathcal{T}是字符串集合(无论有限与否),定义\mathcal{S}\mathcal{T}的乘积为:

\mathcal{ST}=\lbrace s\in\mathcal{S},t\in\mathcal{T}|st\rbrace

对于任意语言\mathcal{L},有

\mathcal{L}\varLambda=\varLambda\mathcal{L}=\mathcal{L}

EXAMPLE
\mathcal{S}=\lbrace a,aa,aaa\rbrace,\mathcal{T}=\lbrace bb,bbb\rbrace,则有

\mathcal{ST}=\lbrace abb,abbb,aabb,aabbb,aaabb,aaabbb\rbrace

语言及其对应的正则表达式

对于每个正则表达式,我们都可以定义与其对应的语言

DEFINITION
以下步骤定义了与任意正则表达式相关的语言
1. 对于任意只有一个字母的正则表达式\boldsymbol{x},其对应的语言就是\lbrace x\rbrace,而\boldsymbol{\Lambda}对应的语言就是\lbrace \Lambda\rbrace
2. 如果\footnotesize\footnotesize \varGamma_1是与\mathcal{L_1}对应的正则表达式,而\footnotesize \varGamma_2是与\mathcal{L_2}相关的正则表达式,则:
1. language(\footnotesize \varGamma_1\footnotesize \varGamma_2)=\mathcal{L_1L_2}
2. language(\footnotesize \varGamma_1+\footnotesize \varGamma_2)=\mathcal{L_1+L_2}
3. language(\footnotesize \varGamma_1^\ast)=\mathcal{L_1}^\ast,注意此处后者的\ast代表取闭包

以上的规则定义了和每一个正则表达式相关联的语言,因为其中包含了正则表达式定义本身的每个规则,并且指定了对应规则所对应的语言,我们按照正则表达式的递归定义去构建一个正则表达式的时候,也就同样构建了一个关联于该正则表达式的语言

  根据上面的内容,我们可以引申出两个重要的问题:

  1. 我们已经见过两种正则表达式对应同一种语言的情况了(比如(a+b)^\ast=(a+b)\ast ab(a+b)^\ast+b^\ast a^\ast),那么是否有一种算法能够判定两种正则表达式是否对应了同一种语言呢?(该问题会在以后介绍)
  2. 上面的定义告诉了我们每个正则表达式都有与之关联的语言,那么是否所有的语言都可以被正则表达式定义呢?,接下来会给出一个定理证明所有有限的语言都可以被正则表达式定义。(同样在以后也会讨论不能被正则表达式定义的语言)

书中有很令人感慨的一段发言,里面提到,完全没有任何手段来试图理解一个正则表达式真正表达的含义,"We may be centuries away from being able to do that, if it can be done at all.",然而这本书是1986年的,现在是2021年4月9日,35年过去,依赖机器学习,NLP和人工智能领域的知识来让电脑自主学习并分辨有限自动机和正则表达式已经并非是痴人说梦,甚至已经可以付诸实现。时光荏苒,35年前无法想象的事情已经在现在触手可及,真的再过几百年后,计算机领域又将会是什么样子,人工智能又将会是什么样子?前途似海,未来可期。

有限语言与正则

定理5
如果\mathcal{L}是一个有限语言(前文提到过,有限语言指单词数量有限的语言),则\mathcal{L}可以被正则表达式定义,换言之,所有有限语言都是正则的
证明
证明过程非常简单,既然一个语言是有限的,那么我们就可以把它的所有单词所对应的正则表达式罗列出来,并用+号连接,就构成了一个对应该语言的正则表达式
对应这种语言的正则表达式并不一定是唯一的,但是我们只需要证明有任意一个存在即可


乱我心者,今日之日多烦忧