Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms
Подождите немного. Документ загружается.
Logic,
Automata,
and
Algorithms
Mark
A.
Aiserman
Leonid
A.
Gusev
Lev
1.
Rozonoer
lrina
M.
Smirnova
Aleksey
A.
Tal’
Institute
of
Automation and Remote Control
Academy
of
Sciences
of
the
USSR,
Moscow
Translated
by
Scripta Technica, Inc.
TRANSLATION EDITOR
George
M.
Kranc
City University
of
New York
New York, New York
ACADEMIC
PRESS
1971
NEW
YORK
AND
LONDON
COPYRIGHT
0
1971,
BY
ACADEMIC
PRESS, INC.
ALL RIGHTS RESERVED
NO
PART OF THIS
BOOK
MAY BE REPRODUCED
IN
ANY FORM,
BY PHOTOSTAT, MICROFILM, RETRIEVAL SYSTEM, OR ANY
OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM
THE PUBLISHERS.
ACADEMIC
PRESS,
INC.
I
I1
Fifth
Avenue,
New
York,
New
York
10003
CJtiited
Kittgdorii
Edition
published
by
ACADEMIC
PRESS,
INC.
(LONDON)
LTD.
Berkeley
Square
House,
Lrmdon W1X
6BA
LIBRARY
Or
CONGRTSS CATALOG CARD
NUMBER:
72-153664
Originally published
as:
“Logika,
Avtomaty, Algoritmy” by
Gosud.
Iz
-
vo
Fiziko
-
Matem. Literatury (State Press
for
Physical and Mathematical Publications),
Moscow,
1963
PRINII-D
IN
IHF
UNIIED
SlAlES
OF AMrRlCA
Contents
PREFACE
..................................................
ix
TRANSLATOR'SNOTE
..........................................
X
INTRODU~ION
..............................................
xi
1
.
Elements
of
Mathematical Logic
1.1. Introductory Notes
...............................
1
1.2.
Basic Concepts
...................................
2
1.3.
Propositional Calculus
.............................
7
1.4. Two-Valued Predicate Calculus
......................
23
2
.
Engineering Applications
of
Propositional Calculus
2.1. Combinational Relay Switching Circuits
...............
27
2.2. Analysis of Combinational Relay Switching Circuits
......
33
2.3. Synthesis of Combinational Relay Switching Circuits
.....
37
Practical Devices
.................................
40
Logical Functions
................................
51
2.4.
2.5.
Other Methods for Converting Logical Functions into
The Problem
of
Minimization of Devices Performing
3 .
Finite Automata and Sequential Machines:
Basic
Concepts
3.1. Discrete Time and Discrete Time Moments
.............
58
3.2. On Dynamical Systems
.............................
60
3.3,
Finite Automata
.................................
62
3.4.
Sequential Machines
...............................
66
Sequential Machines
...............................
69
3.6.
Recording the Operation of an Automaton
.............
75
3.7. On the Restriction of Input Sequences
.................
84
3.5.
Techniques for Defining Finite Automata and
4
.
Abstract Structure
and
Nets
4.1.
The Concept of Substitution of Sequential Machines
......
86
4.2. The Abstract Structure
of
the Automaton
..............
91
4.3.
Nets
...........................................
97
Abstract Aggregates of Automata and Sequential
Machines
.......................................
107
4.4.
4.5.
Abstract Neurons and Models of Neural Nets
...........
109
V
vi
CONTENTS
5,
Technical Embodiment
of
Finite Automata and Sequential
Machines
5.1.
5.2.
5.3.
5.4.
Two
Methods for Technical Realization
of
Finite
Automata and sequential Machines
...................
116
Aggregative Design of Finite Automata and
Sequential Machines.
..............................
1
17
Synthesis
of
Finite Automata and Sequential Machines
by Utilizing Inherent Delays as Well as Feedback.
........
124
Huffman’s Method and Realization
...................
130
6.
Autonomous Finite Automata and Sequential Machines
6.1.
6.2.
What Autonomous Finite Automata and Sequential
Machines “Can
Do”
...............................
144
Synthesis
of
the Bistable Structure
of
an Autonomous
Sequential Machine
...............................
150
7.
Representation
of
Events in Finite Automata and Sequential
Machines
7.1.
Statement of the Problem
..........................
159
7.2. Events. Representation of Events.
....................
160
7.3. Operations on Sets of Input Sequences
................
163
7.4. Representability of Regular Events
...................
17 1
7.5.
Regularity of Representable Events..
.................
176
7.6.
Do
Irregular (Unrepresentable) Events Exist?
...........
18
1
7.7. What a Finite Automaton “Can Do”
..................
185
8.
Recognition
of
Realizability
of
a Given Specification. Abstract
Synthesis
of
Finite Automata and Sequential Machines
8.1. Statement
of
the Problem
..........................
187
8.2. The Case Where the Specification Enumerates the
Required Input-Output Correspondences.
..............
189
8.3. Algorithmic Unsolvability
of
the Problem of Recognition
of
Representability
of
Recursive Events
...............
203
8.4.
Synthesis
of
Finite Automata and Sequential Machines in
the Language
of
Regular Expressions.
.................
207
9.
Equivalence and Minimization
of
Sequential Machines
9.1.
9.2.
9.3.
9.4.
9.5.
The Problem
of
Recognition
of
Equivalent States
........
219
Algorithmic Unsolvability of the Generalized Recognition
Problem
of
Recognition of Equivalence of States.
.........
221
Recognition
of
the Equivalence of States in the Case of
an
Unrestricted Set of Input Sequences
...................
223
Recognition of Equivalence
of
States for the Case
of
Input
Sequences
of
Limited Length
.......................
230
Equivalence, Mapping and Minimization
of
Sequential
Machines
................
......................
235
CONTENTS
vii
9.6.
9.7.
9.8.
9.9.
Minimization of a Sequential Machine with an
Unrestricted Set
of
Allowable Input Sequences
.........
237
Minimization of a Sequential Machine When It
Operates as a Finite Automaton
.....................
241
Minimization
of
Machines in the Case of Aufenkamp-
Type Constraints
................................
246
Another Definition of Equivalence of Sequential
Machines
......................................
254
10
.
Transformation of
Clock
Rates of Sequential Machines
10.1.
General Considerations Regarding Clock Rate
Transformation
.
Definition of Representation and
Reproduction
...................................
260
Examples
of
Representation and Reproduction
.........
266
Reproduction of a Slow Machine
on
a Fast One in the
Case When the Cycle
of
the Slow Machine
Is
Governed
by the Change
of
Input State
.......................
269
Minimization
of
the s-Machine of Section
10.3
.........
274
10.2.
10.3.
10.4.
11
.
Determination of the Properties of Sequential Machines from
Their Response to Finite Input Sequences
11.1.
11.2.
11.3.
11.4.
Definitions and Statement
of
Problem
................
284
Determination of Equivalence of States of s-Machines
from Their Response to Finite Inputs
................
286
Multiple Experiments on Sequential Machines
..........
291
Simple Experiments on Sequential Machines
...........
294
12
.
Algorithms
12.1.
12.2.
12.3.
12.4.
12.5.
12.6.
12.7.
12.8.
12.9.
12.10.
12.11.
12.12.
12.13.
Examples of Algorithms
..........................
304
General Properties of Algorithms
...................
308
The Word Problem in Associative Calculus
.............
310
Algorithms in an Alphabet
A
.
Markov’s Normal
Algorithm
.....................................
314
Reduction of any Algorithm to a Numerical Algorithm
.
Godelization
...................................
321
Elementary and Primitive Recursive Functions
.........
324
Predicates
.
Minimalization
.........................
333
A Computable But Not Primitive Recursive Function
....
338
General Recursive Functions
.......................
339
Explicit Form of General Recursive Functions
.........
343
Church’s Thesis
.................................
348
Recursive Real Numbers
.......................
Recursively Enumerable and Recursive Sets
...........
352
CONTENTS
...
Vlll
13.
Turing Machines
13.1.
13.2.
13.3.
Description
and
Examples
of
Turing
Machines.
.
. . .
. . .
. .
.
355
The Composition
of
Turing Machines
. . .
. .
. . .
.
.
.
.
.
. . .
.
363
Computation
on
Turing Machines
. . .
.
.
. . .
.
. .
.
. . .
. . . .
366
Conclusion
1.
2.
What Can a Finite Automaton or a Sequential Machine
“Do”?
.........................................
377
The Synthesis
of
a
Practical Device Realizing
a
Finite
Automaton or Sequential Machine
. .
.
.
.
.
.
.
. .
.
.
.
,
.
.
.
. .
379
Problems
............
.
.
. .
. . . .
.
.
.
387
.
. .
. .
. . .
388
...................
391
....................
392
_ _
..................................
394
..........
Chapter
10..
.
.
. . . . .
. .
.
.
.
. .
. .
Bibliography
..
...........................................
409
Addenda
to
Bibliography
. .
.
.
. . . .
. .
.
. .
. . .
. .
. .
. .
. .
.
. .
.
. . . . . .
.
.
.427
Index
....................................................
430
Preface
This book deals with the general theory of finite automata and
sequential machines,
a
subject of great current theoretical and
practical importance and one likely to have an even greater impact
in the future.
In writing this text,
we
had in mind
a
wide audience.
We
natur-
ally hoped it would be useful to specialists in switching or digital
computer theory and design. Such persons
are
alreadyfamiliar with
the necessary mathematical techniques, that
is,
propositional
cal-
culus, general concepts of predicate calculus, and the fundamentals
of the theory of algorithms (theory of recursive functions). For
them, the book may serve
as
a
reference on fundamentals. But our
primary audience
is
the beginner whose mathematical training
is
confined to fundamentals of calculus, differential equations, and
mathematical physics. Aside from engineering students, such read-
ers
may include specialists in automation, remote control and com-
munications, that
is,
those branches of engineering
where
lack
of
fundamentals of mathematical logic and
the
theory of algorithms may
preclude
the
solution of
a
variety of problems.
In addition,
we
would
like
to think that the potential beneficiaries
may include the mathematician who
is
not alogician,
as
well
as
the
physicist, physiologist and biologist interested in the applications of
the theory of finite automata and sequential machines to idealized
models,
such
as
those of nets of nerves. Basically, however, the
book
is
intended for engineers, which
is
why,
in discussing some
problems of logic and algorithmic theory,
we
preferred to forego
mathematical rigor and concentrate on
the
clarity
of
exposition.
Thus, the objective of
this
bookis tointroduce the reader to
this
new field and familiarize him with the basic concepts and the ways
in which particular problems
are
stated,
as
well
as
those solutions
which have been obtained
so
far.
In the presentation, our own
re-
sults
are
intertwined with those obtained from the relevant
litera-
ture.
Since this text
is
designed for
a
diversified audience,
we
could
not organize it in
a
manner that would suit any special group. The
ix
X
PREFACE
disposition of subject matter
is
thus
a
compromise between con-
tending interests. In general, the material
is
arranged in order of
increasing difficulty, and each reader should thus proceed accord-
ing to
his
own needs and background.
We
would, however,
like
to
offer several suggestions:
1.
The reader who
is
completely unfamiliar with the subject but
seeks
detailed information should follow the sequence pre-
sented
in
the book.
2.
The reader interested only in
a
general acquaintance with the
subject should
read
the first seven chapters consecutively,
followed by Chapter 12; after this he may glance through
Chapter 13, and finish by reading Chapters
8,
9,
10,
and
11.
3.
The reader familiar with
the
fundamentals
of
mathematical
logic and
its
technical applications
is
advised to begin with
Chapter 3.
4.
Finally, the mathematician interested in engineering applica-
tions may
safely
omit Chapters
1,
12,
and 13.
Sections 2.5 and
8.4
deal with the special problems of minimiza-
tions of Boolean functions and the realization of finite automata, de-
fined in the language of regular expressions; these sections (which
go beyond the basic principles of the general theory of finite auto-
mata and sequential machines)
were
written, at the author’s request,
by
V.D.
Kazakov and
O.P.
Kuznetsov, respectively.
The authors would welcome all comments and suggestions.
TRANS
LATO
R’S
NOTE
This translation
of
the original Russian edition contains problems, additions,
and revisions prepared by the author for the English edition.
Introduction
“Finite automaton’’ and “sequential machines”
are
two
tradi-
tional terms that
are
widely used to designate
a
very simple
class
of dynamical systems. The theory of this
class
evolved
as
a sep-
arate entity for the following two reasons:
1.
These dynamical systems
are
frequently employed in tech-
nology, particularly in automatic and remote control and computer
engineering (digital computers
are
a
special
case
of this
class).
The
needs of modern technology have therefore prompted an intensive
study of
the
general relationships governing this class, in order to
develop methods of analysis and of optimal synthesis of these dy-
nami cal systems
.
2.
The continuing progress in science and technology, particu-
larly in computers, increasingly poses questions such
as:
What can
a
machine ccdo” and what
is
it
incapable of “doing”? Could
a
ma-
chine perform any algorithm? In principle, could
a
machine do
something more than merely execute an algorithm? To what extent
is
a
machine capable or incapable of performing functions charac-
teristic
of
a
human brain?
All
attempts at exact formulation of these
questions, let alone finding the answers, hinge uponour definition of
the term
As
of now, it
is
impossible to solve
these
problems in terms of
a
very broad
class
of dynamical systems.
If,
however, we define
a
machine
as
a
restricted
class
of such
sys-
tems-that known
as
“finite
automata” and “sequential machines’
7-
then the questions make sense. They can be exactly formulated and,
in some cases, answered.
There
is
another reason, peculiar to our present
state
of knowl-
edge, which helps maintain interest in systems of this class. The
brain consists of
a
very large number of nerve cells,
or
neurons.
By idealizing
their
properties to some extent,
we
can construct a
mathematical model of the brain-one that
is
valid, of course, only
within the limits of
this
idealization. This model
is
also
a
dynami-
cal
system of the type
we
shall
consider.
Our
expanding knowledge
of neurons and of
the
brain
as
a
whole
has
shown that the above
idealization
is
inadequate and that more complexmodels
are
desir-
able. Nevertheless, the fact remains that within this idealized frame-
xi