Computer Science - Compiler Design - Introduction To The Theory Of Computation (1989 Gurari).pdf

(6215 KB) Pobierz
*More than 150,000 articles in the
search database
*Learn how almost everything
works
 
theory-bk.html
An Introduction to the Theory of
Computation
Eitan Gurari, Ohio State University
Computer Science Press, 1989, ISBN 0-7167-8182-4
Copyright © Eitan M. Gurari
To Shaula, Inbal, Itai, Erez, Netta, and Danna
Preface
1 GENERAL CONCEPTS
1.1 Alphabets, Strings, and Representations
1.2 Formal Languages and Grammars
1.3 Programs
1.4 Problems
1.5 Reducibility among Problems
Exercises
Bibliographic Notes
2.1 Motivation
2.2 Finite-State Transducers
2.3 Finite-State Automata and Regular Languages
2.4 Limitations of Finite-Memory Programs
2.5 Closure Properties for Finite-Memory Programs
2.6 Decidable Properties for Finite-Memory Programs
Exercises
Bibliographic Notes
3 RECURSIVE FINITE-DOMAIN PROGRAMS
3.1 Recursion
3.2 Pushdown Transducers
3.3 Context-Free Languages
3.4 Limitations of Recursive Finite-Domain Programs
3.5 Closure Properties for Recursive Finite-Domain Programs
3.6 Decidable Properties for Recursive Finite-Domain Programs
Exercises
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html (1 of 3) [2/24/2003 1:46:54 PM]
 
 
theory-bk.html
Bibliographic Notes
4 GENERAL PROGRAMS
4.1 Turing Transducers
4.2 Programs and Turing Transducers
4.3 Nondeterminism versus Determinism
4.4 Universal Turing Transducers
4.5 Undecidability
4.6 Turing Machines and Type 0 Languages
4.7 Post's Correspondence Problem
Exercises
Bibliographic Notes
5 RESOURCE-BOUNDED COMPUTATION
5.1 Time and Space
5.2 A Time Hierarchy
5.3 Nondeterministic Polynomial Time
5.4 More NP -Complete Problems
5.5 Polynomial Space
5.6 P -Complete Problems
Exercises
Bibliographic Notes
6 PROBABILISTIC COMPUTATION
6.1 Error-Free Probabilistic Programs
6.2 Probabilistic Programs That Might Err
6.3 Probabilistic Turing Transducers
6.4 Probabilistic Polynomial Time
Exercises
Bibliographic Notes
7 PARALLEL COMPUTATION
7.1 Parallel Programs
7.2 Parallel Random Access Machines
7.3 Circuits
7.4 Uniform Families of Circuits
7.5 Uniform Families of Circuits and Sequential Computations
7.6 Uniform Families of Circuits and PRAM's
Exercises
Bibliographic Notes
A MATHEMATICAL NOTIONS
A.1 Sets, Relations, and Functions
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html (2 of 3) [2/24/2003 1:46:54 PM]
 
theory-bk.html
A.2 Graphs and Trees
B BIBLIOGRAPHY
Index
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html (3 of 3) [2/24/2003 1:46:54 PM]
 
theory-bk-preface.html
[ next ] [ tail ] [ up ]
Preface
Computations are designed to solve problems. Programs are descriptions of computations written for
execution on computers. The field of computer science is concerned with the development of
methodologies for designing programs, and with the development of computers for executing programs.
It is therefore of central importance for those involved in the field that the characteristics of programs,
computers, problems, and computation be fully understood. Moreover, to clearly and accurately
communicate intuitive thoughts about these subjects, a precise and well-defined terminology is required.
This book explores some of the more important terminologies and questions concerning programs,
computers, problems, and computation. The exploration reduces in many cases to a study of
mathematical theories, such as those of automata and formal languages; theories that are interesting also
in their own right. These theories provide abstract models that are easier to explore, because their
formalisms avoid irrelevant details.
Organized into seven chapters, the material in this book gradually increases in complexity. In many
cases, new topics are treated as refinements of old ones, and their study is motivated through their
association to programs.
Chapter 1 is concerned with the definition of some basic concepts. It starts by considering the notion of
strings, and the role that strings have in presenting information. Then it relates the concept of languages
to the notion of strings, and introduces grammars for characterizing languages. The chapter continues by
introducing a class of programs. The choice is made for a class, which on one hand is general enough to
model all programs, and on the other hand is primitive enough to simplify the specific investigation of
programs. In particular, the notion of nondeterminism is introduced through programs. The chapter
concludes by considering the notion of problems, the relationship between problems and programs, and
some other related notions.
Chapter 2 studies finite-memory programs. The notion of a state is introduced as an abstraction for a
location in a finite-memory program as well as an assignment to the variables of the program. The notion
of state is used to show how finite-memory programs can be modeled by abstract computing machines,
called finite-state transducers. The transducers are essentially sets of states with rules for transition
between the states. The inputs that can be recognized by finite-memory programs are characterized in
terms of a class of grammars, called regular grammars. The limitations of finite-memory programs,
closure properties for simplifying the job of writing finite-memory programs, and decidable properties of
such programs are also studied.
Chapter 3 considers the introduction of recursion to finite-memory programs. The treatment of the new
programs, called recursive finite-domain programs, resembles that for finite-memory programs in
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk-preface.html (1 of 4) [2/24/2003 1:46:56 PM]
 
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin