模式语言（形式语言）

在理论计算机科学中，模式语言是一种形式语言，可以定义为一串常量和变量的所有特定实例的集合。模式语言是由DanaAngluin在机器学习的背景下提出的。

给定一个常量符号的有限集合Σ和一个与Σ不相干的变量符号的可数集合X，模式是一个来自Σ∪X的有限的非空的符号串。一个模式的长度p，用|p|表示，只是其符号的数量。所有恰好包含n个不同变量（每个变量可能出现几次）的模式的集合用Pn表示，所有模式的集合用P*表示。替换是一种映射f：P*→P*，使得f是一个关于字符串连接的同态性（⋅），形式为：∀p,q∈P*.f(p⋅q)=f(p)⋅f(q);f是非递减的，形式为：∀p∈P*.f(p)≠ε，其中ε表示空字符串；f尊重常数，形式为：∀s∈Σ.f(s)=s。如果p=f(q)，对于某些模式p，q∈P*和某些替换f来说，那么p被称为比q更不一般，写成p≤q；在这种情况下，必然|p|≥|q|成立。对于一个模式p，它的语言被定义为所有不那么一般的模式的集合，这些模式只由常数建立，正式地。L(p)={s∈Σ+:s≤p}，其中Σ+表示Σ中所有有限的非空符号串的集合。例如，使用常数Σ={0,1}和变量X={x,y,z,...前者的一个实例是00z100z0z1和01z101z1z1，它是通过将x分别映射到0z和1z，以及将其他每个符号映射到其自身的替换而得到。00z100z0z1和01z101z1z1也都是xxy的实例。事实上，L（0x10xx1）是L（xy）的一个子集。模式x0和x1的语言是分别表示偶数和奇数的所有位串的集合。xx的语言是所有可通过将一个比特串与自身连接而得到的字符串的集合，例如，00,11,0101,1010,11101110∈L（xx）。

对于一个任意的字符串s∈Σ+和模式p，决定s是否∈L(p)的问题是NP-完备的（见图），因此对于任意的模式p，q，决定p≤q的问题也是如此。模式语言的类别在......下不是封闭的。联合：例如，对于Σ={0,1}如上，L(01)∪L(10)不是模式语言；补：Σ+L(0)不是模式语言；相交。L(x0y)∩L(x1y)不是一种模式语言；Kleeneplus。L(0)+不是模式语言；同构：f(L(x))=L(0)+不是模式语言，假设f(0)=0=f(1)；反同构：f-1(111)={01,10,000}不是模式语言，假设f(0)=1和f(1)=11。串联。

L(p)⋅L(q)=L(p⋅q);反转。如果p，q∈P1是正好包含一个变量的模式，那么当且仅当L(p)⊆L(q)时，p≤q；同样的等价关系对等长的模式也成立。对于不同长度的模式，上面的例子p=0x10xx1和q=xy表明L(p)⊆L(q)可能成立而不意味着p≤q。然而，任意长度的两个模式p和q，当且仅当它们在一致的变量重命名之前是相等的，就会生成相同的语言。每个模式p是其生成的语言L(p)中所有字符串的共同概括，是(⋅)的关联性。

在精炼的乔姆斯基层次结构中，模式语言类分别是单子语言和索引语言的适当的超类和子类，但与两者之间的语言类不可比；由于后者，模式语言类在下面的表格中没有明确显示。模式语言类与有限语言类、正则语言类和无语境语言类是不可比拟的。模式语言L(xx)不是无语境的(因此既不是规则的也不是有限的)，这是由于抽水马桶的原因；有限的(因此也是规则的和无语境的)语言{01,10}不是模式语言。每个单子语言都是一个模式语言，由一个没有变量的模式生成。每个模式语言都可以由一个索引语法产生：例如，使用Σ={a,b,c}和X={x,y}，模式axbycxayb由一个具有非终端符号N={Sx,Sy,S}的语法产生。∪X，终端符号T=Σ，索引符号F={ax,bx,cx,ay,by,cy}，起始符号Sx，以及以下生产规则。