词条 | 抽象语言族 |
释义 | chouxiang yuyanzu 抽象语言族(卷名:电子学与计算机) abstract family of languages 某些代数运算下具有封闭性的形式语言类,简称AFL。抽象语言族是用代数方法研究形式语言理论的重要成果。 基本定义 令 ![]() ![]() ![]() ![]() 在同态、逆同态和与正则语言相交下保持封闭的语言族称为满三重组。对并运算封闭的满三重组称为满半AFL。对乘幂闭包封闭的满半 AFL称为满AFL。从一个语言族 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 判别准则 把非确定型有限自动机中的输出字母推广为输出字母串,所得的装置称为a转换器。把一个语言L的所有语句作输入,全体输出语句的集合即构成新语言L′。 一个语言族成为满三重组的充分必要条件是它在 a转换器运算下是封闭的。对 ![]() ![]() ![]() ![]() 一个语言族成为 AFL的充分必要条件是它在并运算、无空字乘幂闭包、无空字正则置换、与正则语言相交及有界同态下是封闭的。 一个语言族成为满 AFL的充分必要条件是它在并运算、乘幂闭包、正则置换、与正则语言相交及同态映射下是封闭的。 抽象接收器族 类似于从个别的语言到抽象语言族,从个别的自动机(接收器)出发也可得到相应的抽象接收器族,简称AFA。AFA接受语言族有两种方式。如果只要求该AFA最后进入终止状态,则接受的语言族正好是满半AFL。如果除了要求AFA进入终止状态外,还要求它的存储同时变空,则接受的语言族正好是满AFL。 乔姆斯基分层的四族语言 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。