[形式语言及其与自动机的关系]·科学社版

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