计算理论研习资料搜集一——自动机与形式语言

计算理论三大部分（自动机、可计算性和复杂性）之一——自动机

《Automata and Formal Languages》
Spring 2005
Juhani Karhum¨aki

Preface
Theory of formal languages (or automata) constitutes建立 a cornerstone of theoretical computer science. However, its origin and motivation come from different sources:
形式语言（或自动机）理论的发现为计算机理论科学建立一个重要的里程碑。但是，形式语言理论创建的最初目的却来自不同的学科：
1. Switching circuits as models for electrical engineers.
电子工程的开关电路模型；
2. Grammars as models for the structure of natural languages (Chomsky, 1956).
语法作为自然语言结构的模型；
3. Models for biological phenomena:
为生物现象建模：
Neural networks which lead to finite automata (McCulloh, Pitts, 1943).
研究神经网络的有限自动机
Lindenmayer systems as models for the growth of organisms (Lindenmayer, 1968).
为有机体的生长过程建模的L系统
4. Models in different parts of theory of programming languages:
为程序设计语言的不同部分建模：解释、编译、文本编辑等；
parsing, compiling, text editing, ...
5. Models for mathematical (and philosophical) questions of computability (Turing,1936; Post).
数学或哲学和可计算性问题模型。

The above list also provides examples of applications of formal languages. Other newer application areas are cryptography and computer graphics.
以上所列的为形式语言的的一些应用。此外新的应用包括密码学和计算机图形学。

Formal language theory is part of discrete mathematics having connections to manyother fields:
Algebra Logic Combinatorics Computability
└──────┸─────┬────┸────────────┚
　　 ┷
　　　Formal languages
In this course we concentrate on languages (e.g. sets of words) described by finite automata, context-free grammars and Turing machines.
在这本书中我们集中讲述由有限自动机、上下文无关文法和图灵机所描述的“语言”（单词的集合）。
Literature:
Berstel, J.: Transductions and Context-Free Languages, Teubner, 1979.
Harrison, M.A.: Introduction to Formal Language Theory, Addison-Wesley, 1978.
Hopcroft, J.E. and Ullman, J.O.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
Davis, M. and Weyuker, E.J.: Computability, Complexity and Languages, Academic Press, 1983.
Lewis, H.R. and Papadimitriou, C.H.: Elements of Theory of Computation, Prentice Hall, 1981.
Salomaa, A.: Formal Languages, Academic Press, 1973.

----------------------------------------
《Problem Solving in Automata, Languages, and Complexity》
Ding-Zhu Du
Ker-I KO

Preface
Over the past twenty years, automata and formal languages have become the standard introductory theory course in both the undergraduate and graduate curricula of computer science. The subjects studied in such a course include automata theory, formal languages, and models of computation. For a more advanced graduate course, computability theory and computational complexity theory are also covered. Whereas these materials are fundamental in many different areas of computer science, this course also offers a unique opportunity for students to learn various mathematical tools to deal with nonstandard, abstract objects.
在过去的二十年里，自动机和形式语言成了计算机科学研究生和本科生标准的导论性课程。这些课程讲述自动机、形式语言和计算模型的理论。高级课程中还包括了可计算理论和计算复杂性理论。这些都是计算科学各研究领域的基础性概念，本课程还为同学们学习和理解这些非标准的抽象的概念打下坚实的数学基础。

This book is designed for such a course, with the emphasis on problem solving. It is commonly recognized that the best, if not the only, way to
learn a mathematics subject is through extensive problem-solving experience.
By attacking the problems directly, one not only learns techniques and tools to solve the problems, but also consolidates巩固 understanding of the underlying concepts. Theory of computation is, by nature, an abstract discipline, and the problem-solving approach appears to be most helpful.
本书与其它教材不同之处在于我们强调问题解决的实践。通过对解决问题的实践经验来学习数学虽然不能说是学习数学的最好方法，但应该是最好方式之一。通过直接解决问题，我们不仅可以学到解决问题的技术和工具，还可以巩固对相关概念的理解。计算理论的本身就是抽象的学科，所以用问题决定的方法来学是很有帮助的。

In this book, we collected a rich variety of examples, ranging from elementary questions about basic definitions and concepts, to advanced ones that employ more sophisticated mathematical tools. The proof ideas and techniques are usually explained in a constructive way, often omitting the routine induction proofs. However, for more difficult questions, the complete, rigorous严格 proofs are also presented. A star sign (*) next to an example or an exercise indicates that it is a more advanced question, and may be skipped in the first reading.
在书中，我们搜集了大量不同的例子，从基础概念的定义的基本问题到使用复杂数学工具的高级问题都有。书上定理的证明我们一般只通过构造性方法来解释，省去冗长的证明过程。不过，在一些复杂问题上，我们还是使用的严格的详细的证明方式。书中带星号的为高级内容，按需阅读。

Because the emphasis of the book is problem solving, we only include the most common topics in theory of computation: finite-state automata,
context-free grammars, Turing machines, recursive and recursively enumerable languages, complexity classes, and NP-completeness. In particular, for formal languages, we limit ourselves to the basics in regular and context-free languages, and omit deterministic context-free languages and various parsing techniques.
因为我们强调问题的解决，所以本书中只讲述了计算理论的最常用的主题：有限状态机、上下文无关文法、图灵机、递归和递归迭代语言、复杂类和NP完备。特别地，在讲述形式语言时，我们只讲述正则语言和上下文无关语言，而省去了确定上下文无关语言和不同的解析技术。

For computability theory, our approach is a traditional one: we use Turing machines as a basic model, and develop the notion of computability through the rich, flexible language of primitive recursive functions. Comparisons with high-level language constructs are also included, when appropriate.
至于可计算性理论，我们使用传统方式来讲述：我们使用图灵机作为基础的模型，然后有原始递归函数的丰富的灵活的语言建立一套可计算性的符号？在适当的地方，我们还会与高级语言构建的方面进行对比学习。
The authors have used this book in a number of different classes. In a one-semester undergraduate course, we usually cover most of Chapters 1 to 3, and the first half of Chapter 4, skipping most starred examples. In a two-semester sequence, starred examples may be covered, and an additional chapter (e.g., Chapter 7) may be added. In a more advanced graduate course emphasizing computability and complexity theory, we typically cover Chapters 4 to 7, skipping some starred proofs in Chapter 6.

We are grateful to our colleagues and students for their suggestions and criticism on the earlier drafts of this book. We owe special thanks to Xiu zhen Cheng and Dean Kelley, who read the manuscript carefully and made a number of corrections.