抽象语族

在计算机科学中，特别是在形式语言理论领域，抽象语族是一个抽象的数学概念，概括了正规语言、无语境语言和可递归列举语言以及科学文献中研究的其他形式语言家族的共同特征。形式定义一个形式语言是一个集合L，对它来说，存在一个有限的抽象符号集Σ，使得{displaystyleLsubseteqSigma{*}}，其中*是Kleene星形。，其中*是Kleene星形操作。一个语言家族是一个有序的对(Σ,Λ){displaystyle(Sigma,Lambda)}，其中*是Kleene星运算。，其中Σ是一个无限的符号集；Λ是一个形式语言集；对于Λ中的每个L，存在一个有限子集Σ三元组是一个在无e同构、反同构和与常规语言相交下封闭的语言家族。一个完整的三元组，也被称为锥体，是一个在任意同构下封闭的三元组。一个（全）半AFL是一个在联合下封闭的（全）三重体。一个（全）AFL是一个（全）半AFL，在连接和Kleeneplus下封闭。

以下是研究抽象语言家族的一些简单结果。在乔姆斯基的层次结构中，常规语言、无语境语言和可递归列举语言都是全AFL。然而，上下文敏感语言和递归语言是AFLs，但不是完全的AFLs，因为它们在任意同构下不封闭。正则语言家族包含在任何锥体中（全三体）。其他类别的抽象族可以通过在其他操作下的闭合来识别，如洗牌、反转或替换。

南加州大学的SeymourGinsburg和哈佛大学的SheilaGreibach在1967年的IEEE第八届开关和自动机理论年度研讨会上发表了xxx篇AFL理论论文。