自动机理论
自动机理论
automata theory
数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象的装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统，这样的抽象自动机可以用来检验输入的符号串是不是语言中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收它。如图所示： 自动机可分为有限自动机、后进先出自动机、线性有界自动机、图灵机等几种。它们对语言的识别能力各不相同。 美国语言学家N.乔姆斯基等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④ 若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。 这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。这是语言学对于现代自然科学发生影响的一个明证。 （冯志伟）
Trackback
你可以使用这个链接引用该篇文章 http://publishblog.blogchina.com/blog/tb.b?diaryID=155530
回复
|
- 评论人：anonymous
2006-08-30 15:54:52
|
|||
那么，如何证明一个自动机呢？自动机在计算机中用的很多，那么在计算机中画自动机的目的又是什么呢？用自动机来描述的目的又是什么呢？有谁能提供以下思路和例证？证明自动机的目的是什么呢？自动机在项目中证明是否需要？它在项目中的作用又是什么敬请各路高手指点？ |
||||
