An Introduction to Formal Languages and Automata
An Introduction to Formal Languages and Automata
复制标题
形式语言和自动机简介
DOI：
10.1093/comjnl/35.2.176
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
K. Moody
中科院分区：
文献类型：
--
作者：
K. Moody
这本书的序言将其确定为“计算理论”的介绍，与ACM课程78中的CS 16课程密切相关。作者的目标是让学生熟悉计算机科学的基础知识，并教授以后有用的材料：虽然数学定理被精确地陈述，但很少给出形式化的证明。根据我的经验，这是一门很难教的课程，因为学生在数学准备的程度和他们对抽象方法的准备程度上都有很大的差异。这里的解决方案是通过大量的实际例子和练习来培养处理抽象计算结构所需的技能，主要集中在语言和自动机上。仅包含递归函数理论的基本元素，在完全由定义组成的四页中。复杂性理论几乎没有触及：最后一节引用了一些主要结果，参考了Hopcroft和Ullman的Intro。
The preface to the book identifies it as an introduction to the'Theory of Computation', corresponding closely to course CS 16 in the ACM Curriculum 78. The author's stated aim is to familiarise students with the foundations of computer science, and to teach material that will be useful later: though mathematical theorems are stated precisely, formal proofs are seldom given.In my experience this is a difficult course to give, since students vary greatly both in their degree of mathematical preparation and in their readiness to commit themselves to an abstract approach. The solution here is to develop the skills needed to handle abstract computational structures by a wealth of practical examples and exercises, concentrating on languages and automata for the most part. Only the basic elements of the theory of recursive functions are included, in four pages that consist entirely of definitions. Complexity theory is hardly touched on: the final section quotes some of the major results, giving references to Hopcroft and Ullman's Intro-