Elaine Rich - Automata, Computability and Complexity.pdf
(
112238 KB
)
Pobierz
Automata,
Computability
and Complexity
THEORY AND APPllCATIONS
Elaine Rich
----
PEARSON
Prentice
Hall
Upper
Sadd
le
River NJ 07458
Library or
Congrcss Cataloging-in-Publication
Data on File
Vice Pres
id
cnt
and Edi
tori
al
Director,
ECS:
Marcia .l.
I-Iorlon
Executive Editor:
Tra
ey
DlIl7kelb
erger
Assislant
Editor:
Carole
Sn
yder
Editorial
Ass
istant
:
ReeA lln
e
Da
vis
Managing
Editor:
Seo
ll
Disollno
Producti
on Ed
itor:
J?ose Keman
Director
01'
Crea
tive
Services:
Palll
Belfanti
Crea
tive Director:Jllan
Lopez
Cover
Designer:
Mavreen Eide
Man
aging Edi
tor,AV
Management
and
Productio n:
Patrieia Bllrns
Art
Editor:
C
rego ry
Dill/es
Director,
Im
age
Reso
urce
Ce
nter:
Melinda Reo
Manager, Ri
ghts anel
Permi
ss
ions:
Zina Arahia
Manager, Visual
Resea
rch:
Belh Brenze!
Manager,
Cover
Vi
sual
Research
ami
Permissions:
Karen
Sanatar
Manufacturing Manage r,
ESM:
Alexis
Heydl-Long
Manllfa
cturing
Buyer:
Lisa MeDowell
Mark
eting
Man
age
r:
Maek Pallerson
•
..
:
•
©
2008
Pea rson
Ed
ucation
,
Inc.
Pem'son
Prentice Hall
Pcarsol1 Edllcation
,
ln
c.
Uppe
r
Sadell
e
River, NJ 07458
All rights reservcel. No part
01'
lhis
book
may
be reproeluced
in
any
form
or
by
any
ll1
ea
ns,
withoul permi
ssion
in wril-
in
g
from the I ublisher.
Pea
rso n
Prentice
Hall
n
l
i
a
traele mark
01'
Pea
rson
Ed
uca tion. In
e.
All
oth
er
trael mark
s or
proeluct names
are
the propert
y
01'
their
respecti
ve
owne
rs.
The
allth
or anel
publishe r
01'
lhis book
have
lIseelth
ei
r
best
errons
in
preparing
thi
s
book. Th
ese
efforts
inelude the ele-
velopme
nt
,
research,
anel
testin
g
of
th
e
theori
es
and
programs
to
eletermin
e
th
eir
effeetivencss.
TI1
C
auth or and
pub-
li
'her
mak
e
11
0
warrant
y
0
1'
any
kind
,
expressed or
impli
eel
,
with regard
to
th
ese
prog rall1s
or
th
e
elocllmentat
ion
contained
in
this book. The
auth
or anel
publi
sher sha
ll
not be
liabl
e
in
an)' event
for
incident
al o
r
ons
quenti
al
ela
m-
ages
in
co
nn
ectio
n
with,
01'
arising
out of,
the
furni
shing,
perform
ance,
01'
use
0
1'
these
program.
.
Print
ed
in
th
e
Un
it
eel
Slales
01'
All1erie
a
10
9 8
7 6 5
4
3 2
I
ISBN:
0-13-228806-0
ISBN:
978-0-13-228806-4
Pea
rso
n
Eellicat
ion
Uel.
,
London
Pea
rso n
Eelucation
Australi
a
Pty. Lid
.,
Sydn
ey
Pea r
on
Eclucat
ion
Singap
ore,
Pte.
Ltd
.
Pea
rso n
Eelucation
North Asia Ltd.
,
!-Iong
Kon
g
Pearso
n
Educa
ti
ol1
Canada,
II1c.,
Torol1lo
Pea rso
n
Educaci6n
de Mexico, S.A. de
c.v.
Pea
rso l1
Education
-
Japan,
Tokyo
Pea rso n
Educa
tion
Malaysia, Pte. Ltd.
Pea
rso
n
Education,
Inc.,
Upper
Saddle J?ivel';
New
Jersey
CONTENTS
Preface
XIII
XVII
Acknowledgments
Credits xix
PART I: INTRODUCTION
1
1
Why Study the Theory of (omputation? 2
1.1
1.2
The Shelf Life of Programming Tools 2
Applications of the Theory Are Everywhere
5
2
Languages and Strings
8
2.1
2.2
Strings
8
Languages 10
Exercises
19
3
The Big Pieture: A Language Hierarehy
21
3.1
3.2
3.3
3.4
Defining the Task: Language Recognition 21
The Power of Encoding 22
A Machine-Based Hierarchy of Language Classes 28
A Tractability Hierarchy of Language (lasses 34
Exercises 34
4
(omputation 36
4.1
4.2
4.3
Decision Procedures
36
Determinism and Nondeterminism
41
Functions on Languages and Programs 48
Exercises
52
PART 11: FINITE STATE MACHINES
AND REGULAR
LANGUAGES 53
5
Finite State Maehines 54
5.1
5.2
5.3
Deterministic Finite State Machines
56
The Regular Languages
60
Designing Deterministic Finite State Machines
63
iii
Plik z chomika:
Rivit
Inne pliki z tego folderu:
Elaine Rich - Automata, Computability and Complexity.pdf
(112238 KB)
HaskellNotesForProfessionals.pdf
(1943 KB)
MicrosoftSQLServerNotesForProfessionals.pdf
(2705 KB)
MATLABNotesForProfessionals.pdf
(2886 KB)
GitNotesForProfessionals.pdf
(2546 KB)
Inne foldery tego chomika:
Android
Filmy
Gry PC PSX + CRACKI
Muzyka
Programy
Zgłoś jeśli
naruszono regulamin