什么是抽象语言族?

[拼音]：chouxiang yuyanzu

[外文]：abstract family of languages

某些代数运算下具有封闭性的形式语言类，简称AFL。抽象语言族是用代数方法研究形式语言理论的重要成果。

令


_∞为无限字母表，在其任一有限子集


_i上构造语言


。如果任何一组语言｛L_i｝中至少包含一个


，则称｛L_i｝为一语言族。

在同态、逆同态和与正则语言相交下保持封闭的语言族称为满三重组。对并运算封闭的满三重组称为满半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。

乔姆斯基分层的四族语言


₀、


₁、


₂、


₃都是AFL，其中只有


₀、


₂、


₃是满AFL。


₁不是，因为它在一般的同态映射下不封闭。