拼接规则

在数学和计算机科学中，拼接规则是对形式语言的一种转换，它将分子生物学中的基因拼接作用形式化。拼接语言是由拼接规则的反复应用而产生的语言：拼接语言构成了正规语言的一个适当的子集。定义设A是一个字母表，L是一种语言，即自由单体A∗的一个子集。一个拼接规则是A∗元素的四元组r=（a,b,c,d），规则r对L的作用是产生语言r(L)={xady:xabq,pcdy∈L}。.{displaystyler(L)={xady:xabq,pcdyinL.}。如果R是一个规则集，那么R(L)就是由R的规则所产生的语言的联合体。如果R中的(a,b,c,d)意味着(a,b,a,b)和(c,d,c,d)都在R中，则一个规则集R是反身的。

让A={a,b,c}。规则(caba,a,cab,a)应用于有限集合{cabb,cabab,cabaab}，生成正则语言caba∗b。属性所有拼接语言都是正则的。不是所有正则语言都是拼接的。一个例子是{a,b}上的(aa)∗。如果L是字母表A上的正则语言，而z是不在A中的字母，那么语言{zw:w在L}是一种拼接语言。有一种算法可以确定给定的正则语言是否是反身拼接语言。尊重正则语言的拼接规则集可以从该语言的句法单体中确定。