Prentice Hall, 1982. - 417 Pages.
This book is an introduction to theoretical computer science emphasizing two interrelated areas: the theory of computability (how to tell whether problems are algorithmically solvable) and the theory of formal languages (how to design and use special languages, as for algorithms). Automata (idealized computer devices) are used as precise models of computation in studies that have actual computers as their primary application. Other areas, such as semantics and computational complexity, are treated briefly, in an attempt to bring all of theoretical computer science into view.
There are many excellent books in theoretical computer science for the graduate student and the more advanced undergraduate. These are, for the most part, too advanced for students without previous exposure to theoretical issues, even those with experience in programming: The main difficulty is that there are not enough exercises suitable for students confronting theory for the first time. This book seeks to provide a well-rounded and elementary explanation of the issues, and, more important, an adequate supply of exercises at the right level, integrated with the text. A number of groups of exercises are particularly appropriate for beginning students, but exercises for the more advanced or more mathematically inclined students are provided throughout.
This book is an introduction to theoretical computer science emphasizing two interrelated areas: the theory of computability (how to tell whether problems are algorithmically solvable) and the theory of formal languages (how to design and use special languages, as for algorithms). Automata (idealized computer devices) are used as precise models of computation in studies that have actual computers as their primary application. Other areas, such as semantics and computational complexity, are treated briefly, in an attempt to bring all of theoretical computer science into view.
There are many excellent books in theoretical computer science for the graduate student and the more advanced undergraduate. These are, for the most part, too advanced for students without previous exposure to theoretical issues, even those with experience in programming: The main difficulty is that there are not enough exercises suitable for students confronting theory for the first time. This book seeks to provide a well-rounded and elementary explanation of the issues, and, more important, an adequate supply of exercises at the right level, integrated with the text. A number of groups of exercises are particularly appropriate for beginning students, but exercises for the more advanced or more mathematically inclined students are provided throughout.