正则语言的归纳

在计算学习理论中，正则语言的归纳是指从一组给定的例子字符串中学习正则语言的正式描述（例如语法）的任务。尽管E.MarkGold已经表明，并不是每一种正则语言都能以这种方式学习（见极限中的语言识别），但对于各种子类的方法已经进行了研究。本文对这些方法进行了简要介绍。关于更一般的语法的学习，见语法归纳。

正则语言被定义为一个（有限的或无限的）字符串集，可以用一种叫做有限自动机、正则语法或正则表达式的数学形式来描述，所有这些形式都具有相同的表达能力。由于后一种形式主义导致了最简短的符号，所以这里将介绍和使用它。给定一个符号集Σ（又称字母表），正则表达式可以是以下任何一个∅（表示字符串的空集），ε（表示只包含空字符串的单子集），a（其中a是Σ中的任何字符；表示只包含单字符字符串a的单子集），r+s（其中r和s又是更简单的正则表达式。r⋅s（表示r's和s's集合中所有可能的字符串连接的集合），r+（表示r's集合中的字符串的n倍重复的集合，对于任何n≥1），或者r*（同样表示n倍重复的集合，但也包括空字符串，被视为0倍重复的）。例如，使用Σ={0,1}，正则表达式(0+1+ε)⋅(0+1)表示所有具有一个或两个数字的二进制数的集合（允许有前导零），而1⋅(0+1)*⋅0表示所有偶数（没有前导零）的（无限）集合。给定一组字符串（也称为正例），正则语言归纳法的任务是想出一个正则表达式来表示包含所有这些字符串的集合。作为一个例子，给定{1,10,100}，一个自然的描述可以是正则表达式1⋅0*，对应于非正式的表征一个1后面有任意多（甚至可能没有）0。然而，(0+1)*和1+(1⋅0)+(1⋅0⋅0)是另一个正则表达式，表示包含给定字符串的xxx(假设Σ={0,1})和最小的集合，并分别称为琐碎的泛化和欠泛化。一些方法在一个扩展的环境中工作，其中也给出了一组负面的例子字符串；然后，要找到一个正则表达式，产生所有的正面例子，但不产生负面例子。

Dupont等人表明，生成给定输入示例字符串集的所有结构完整的有限自动机的集合形成了一个格子，其中微不足道的泛化自动机和微不足道的泛化自动机分别作为底层和顶层元素。这个格子的每个成员都可以通过适当的等价关系对微不足道的自动机进行因子化来获得。对于上面的例子字符串集{1，10，100}，图片在底部显示了灰色的欠广义自动机Aa,b,c,d，由状态a，b，c和d组成。在状态集{a,b,c,d}上，总共存在15个等价关系，形成一个网格。将每个等价关系E映射到相应的商数自动机语言L(Aa,b,c,d/E)，得到图中所示的部分有序集合。每个节点的语言都用正则表达式表示。该语言可被商数自动机识别为不同的等价关系，所有这些关系都显示在节点的下面。两个节点之间的箭头表示低级节点的语言是高级节点的适当子集。

如果同时给出正反两方面的例子字符串，Dupont等人从正面例子中建立网格，然后研究产生一些负面例子的自动机和不产生负面例子的自动机之间的分离边界。在图片中，分离边界显示为负面例子字符串11（绿色）、1001（蓝色）、101（青色）和0（红色）。Coste和Nicolas提出了一种自己在格子内的搜索方法，他们将其与Mitchell的版本空间范式联系起来。为了找到分离边界，他们在由消极例子引起的状态不平等关系上使用了一种图形着色算法。后来，他们在所有可能的状态融合的集合上研究了几种排序关系。Kudo和Shimbo使用自动机因式分解的表示方法，为下面的方法提供了一个独特的框架（下文略述）。这些方法中的每一个都被证明对应于用于因式分解的特定种类的等价关系。方法k-rever