[拼音]：chouxiang yuyanzu

[外文]：abstract family of languages

某些代数运算下具有封闭性的形式语言类，简称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不是，因为它在一般的同态映射下不封闭。

严正声明：本文由历史百科网注册或游客用户高昂自行上传发布关于» 抽象语言族的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：高昂；本文链接：https://www.freedefine.cn/wenzhan/58777.html