补充资料：机器可表示的形式语言

机器可表示的形式语言
ormal language, machine-representaMe

　　机器可表示的形式语言【匆m..加心口罗，.抽山i世一比p限-，幻加城;加pMa月.ou 03。二，upe及eTan“Mu盆Ma.，.诫J，妙拳可谬别的形式语言(姗chine一托以)邵毯乙ble fonT以】h刀g阳罗) 在执行过程中使机器进人某一特定状态的所有字(协。心)组成的集合.任何一个字的递归可数集都是由某个口1、耐嗯机(T面ngTr以山irle)可表示的一种形式语言.最常见的是考虑递归形式语言的机器识别.有限自动机(autoTnaton，6hite)识别且仅识别正则语言;带堆栈记忆的自动机识别且仅识别上下文无关语言. 当一种形式语言是由无穷字(超字)组成时，称为超语言(sul军rlan今功罗).机器识别超语言的定义与通常见到的定义不同.例如，一个字x属于一个有限自动机吸可识别的超语言，当且仅当自动机在处理x时无穷多次进人某一特定的状态子集. 在研究不是以机器术语给出的具体形式语言时(例如，以形式文法(granu刀ar，fon丁以1)给出的)，经常需要从某个方面刻画语言的复杂性.在这个方向上最通常的途径之一就是寻找能够识别这些语言的一个适当的机器类，并以这类机器的复杂性特征来确定语言的复杂性.另一方面，作为一种惯例，研究具体的某一类机器也包括描述这类机器可表示的形式语言.对机器可表示形式语言的进一步研究是关于这些语言与一些已知的语言类的关系问题，封闭性质(相对于集合论运算等)，以及关于算法和复杂性特点的问题.【补注】亦见形式语言与自动机(伪~】language，王川da以orr坦ta).鲍丰译李廉校
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。