[拼音]：zidongji lilun

[外文]：automata theory

数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象的装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统，这样的抽象自动机可以用来检验输入的符号串是不是语言中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收它。如图所示：

自动机可分为有限自动机、后进先出自动机、线 有界自动机、图灵机等几种。它们对语言的识别能力各不相同。

美国语言学家N.乔姆斯基等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：

（1）若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然；

（2）若某一语言能用线 有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；

（3）若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；

（4）若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。

这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。这是语言学对于现代自然科学发生影响的一个明证。

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