【形式语言及其与自动机的关系】霍普克罗夫特HopcroftJohnE厄尔曼UllmanJeffreyD科学.pdf
形式语言及其与 自动机的关系 J.E.霍普克罗夫特 美 著 J.D.厄尔 曼 莫绍段祥顾秀芬译
译者序著作,着重讲形式语言和自动机的关系,作者首先给出了确定语言的两个基本方法.,一个是文 法,由它可从句子符号S而产生语言中的各句子,另一个是识 别器,即通常所说的自动机,作者从本质上指明了,每一个文 法都有和它等价的自动机.所谓文法与自动机的等价,是指:字w由一文法产生,当且仅当w被自动机接受.这样,有关 文法的性质和相应自动机的性质便可以一起研究,互相补充.更重要的是,通过自动机极易得出相应文法的识别程序,而识 别程序乃是数字电子计算机编译程序的核心,由它可用来完 成对语言句子的语法分析,两者之间有这么密切的关系,这 便是本书所以着重讨论形式语言与自动机的关系的原因,由本书可以
原 一序 形式语言的研究是计算机科学的一个重要领域,形式语 言大约于1956年问世.那时,NoamChomsky给出-一种文 法的数学模型,该文法与当时他所研究的自然语言有关．不 久当,人们便发现了文法的概念对程序员是非常重要的,这样 的研究自然会导致面向语法编译,并产生编译程序之编译程 序的概念．自那以后,研究工作相当高涨,其结果导致了形式 语言和自动机理论之间的关系达到彼此不可分离的程度.