)抽象语言族
某些代数运算下具有封闭性的形式语言类,简称AFL。抽象语言族是用代数方法研究形式语言理论的重要成果。
基本定义 令
∞为无限字母表，在其任一有限子集i上构造语言
。如果任何一组语言｛Li｝中至少包含一个
，则称｛Li｝为一语言族。 在同态、逆同态和与正则语言相交下保持封闭的语言族称为满三重组。对并运算封闭的满三重组称为满半AFL。对乘幂闭包封闭的满半 AFL称为满AFL。从一个语言族
出发，经上述代数运算后得到的闭包分别称为由生成的满三重组、满半AFL和满AFL,以
（）、
()和
（）表之。如果语言族只包含一个语言L，则由生成的结构分别称为满主三重组,满主半AFL及满主AFL。如果把同态限制为无空字同态,即不得把非空字映为空字，则所有以上定义中的“满”字皆应除去。 判别准则 把非确定型有限自动机中的输出字母推广为输出字母串,所得的装置称为a转换器。把一个语言L的所有语句作输入,全体输出语句的集合即构成新语言L′。
一个语言族成为满三重组的充分必要条件是它在 a转换器运算下是封闭的。对
。又对 K≥1构造任意的
。在
上定义同态h为：h(c)＝ε,h(ɑ)＝ɑ(对任意ɑ∈)，则L中任一语句S不会比它的映像h(s)长K倍以上。因此称h为K有界同态。所有的K有界同态统称有界同态。 一个语言族成为 AFL的充分必要条件是它在并运算、无空字乘幂闭包、无空字正则置换、与正则语言相交及有界同态下是封闭的。
一个语言族成为满 AFL的充分必要条件是它在并运算、乘幂闭包、正则置换、与正则语言相交及同态映射下是封闭的。
抽象接收器族 类似于从个别的语言到抽象语言族，从个别的自动机（接收器）出发也可得到相应的抽象接收器族，简称AFA。AFA接受语言族有两种方式。如果只要求该AFA最后进入终止状态,则接受的语言族正好是满半AFL。如果除了要求AFA进入终止状态外，还要求它的存储同时变空，则接受的语言族正好是满AFL。
乔姆斯基分层的四族语言
0、1、2、3都是AFL,其中只有0、2、3是满AFL。1不是,因为它在一般的同态映射下不封闭。
