Издательство Prentice Hall, 1989, -447 pp.
It often seems that mathematicians regularly provide answers well before the rest of the world finds reasons to ask the questions. The operation of the networks of relays used in the first computers is exactly described by Boolean functions. George Boole thereby made his contribution to computer science in the mid-1800s, and Boolean algebra is used today to represent mode TIL (transistor-transistor logic) circuits. In the 1930s, Alan Turing formalized the concept of an algorithm with his presentation of an abstract computing device and characterized the limitations of such machines. In the 1950s, the abstraction of the concepts behind natural language grammars provided the theoretical basis for computer languages that today guides the design of compilers.
These three major foundations of computer science, the mathematical description of computational networks, the limitations of mechanical computation, and the formal specification of languages are highly interrelated disciplines, and all require a great deal of mathematical maturity to appreciate. A computer science undergraduate is often expected to deal with all these concepts, typically armed only with a course in discrete mathematics.
This presentation attempts to make it possible for the average student to acquire more than just the facts about the subject. It is aimed at providing a reasonable level of understanding about the methods of proof and the attendant thought processes, without burdening the instructor with the formidable task of simplifying the material. The majority of the proofs are written with a level of detail that should leave no doubt about how to proceed from one step to the next. These same proofs thereby provide a template for the exercises and serve as examples of how to produce formal proofs in the mathematical areas of computer science. It is not unreasonable to expect to read and understand the material presented here in a nonclassroom setting. The text is therefore a useful supplement to those approaching a course in computation or formal languages with some trepidation.
This text develops the standard mathematical models of computational devices, and investigates the cognitive and generative capabilities of such machines. The engineering viewpoint is addressed, both in relation to the construction of such devices and in the applications of the theory to real-world machines such as traffic controllers and vending machines. The software viewpoint is also considered, providing insight into the underpinnings of computer languages. Examples andapplications relating to compiler construction abound.
This material can be tailored to several types of courses. A course in formal languages that stressed the development of mathematical skills could easily span two semesters. At the other extreme, a course designed as a prerequisite for a formal languages sequence might cover Chapters 1 through 7 and parts of Chapters 8 and
12. In particular, Chapter 8 is written so that the discussion of the more robust grammars (Section 8.1) can be entirely omitted. Section 12.1 is exclusively devoted to results pertaining to the constructs described in the earlier chapters, and Section 12.3 provides a natural introduction to the theory of computability by developing the halting problem without relying on Turing machine concepts.
Preliminaries
Introduction and Basic Definitions
Characterization of FAD Languages
Minimization of Finite Automata
Nondeterministic Finite Automata
Closure Properties
Regular Expressions
Finite-State Transducers
Regular Grammars
Context-Free Languages
Pushdown Automata
Turing Machines
Decidability
It often seems that mathematicians regularly provide answers well before the rest of the world finds reasons to ask the questions. The operation of the networks of relays used in the first computers is exactly described by Boolean functions. George Boole thereby made his contribution to computer science in the mid-1800s, and Boolean algebra is used today to represent mode TIL (transistor-transistor logic) circuits. In the 1930s, Alan Turing formalized the concept of an algorithm with his presentation of an abstract computing device and characterized the limitations of such machines. In the 1950s, the abstraction of the concepts behind natural language grammars provided the theoretical basis for computer languages that today guides the design of compilers.
These three major foundations of computer science, the mathematical description of computational networks, the limitations of mechanical computation, and the formal specification of languages are highly interrelated disciplines, and all require a great deal of mathematical maturity to appreciate. A computer science undergraduate is often expected to deal with all these concepts, typically armed only with a course in discrete mathematics.
This presentation attempts to make it possible for the average student to acquire more than just the facts about the subject. It is aimed at providing a reasonable level of understanding about the methods of proof and the attendant thought processes, without burdening the instructor with the formidable task of simplifying the material. The majority of the proofs are written with a level of detail that should leave no doubt about how to proceed from one step to the next. These same proofs thereby provide a template for the exercises and serve as examples of how to produce formal proofs in the mathematical areas of computer science. It is not unreasonable to expect to read and understand the material presented here in a nonclassroom setting. The text is therefore a useful supplement to those approaching a course in computation or formal languages with some trepidation.
This text develops the standard mathematical models of computational devices, and investigates the cognitive and generative capabilities of such machines. The engineering viewpoint is addressed, both in relation to the construction of such devices and in the applications of the theory to real-world machines such as traffic controllers and vending machines. The software viewpoint is also considered, providing insight into the underpinnings of computer languages. Examples andapplications relating to compiler construction abound.
This material can be tailored to several types of courses. A course in formal languages that stressed the development of mathematical skills could easily span two semesters. At the other extreme, a course designed as a prerequisite for a formal languages sequence might cover Chapters 1 through 7 and parts of Chapters 8 and
12. In particular, Chapter 8 is written so that the discussion of the more robust grammars (Section 8.1) can be entirely omitted. Section 12.1 is exclusively devoted to results pertaining to the constructs described in the earlier chapters, and Section 12.3 provides a natural introduction to the theory of computability by developing the halting problem without relying on Turing machine concepts.
Preliminaries
Introduction and Basic Definitions
Characterization of FAD Languages
Minimization of Finite Automata
Nondeterministic Finite Automata
Closure Properties
Regular Expressions
Finite-State Transducers
Regular Grammars
Context-Free Languages
Pushdown Automata
Turing Machines
Decidability