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 FINITE-MEMORY PROGRAMS
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
