Automata,
Computability
and Complexity
THEORY AND APPLICATIONS
Elaine Rich
PEARSON
~
Prentic~
Upper Saddle River NJ 07458
CONTENTS
Preface xiii
Acknowledgments xvii
Credits xix
PARTI: INTRODUCTION 1
1 Why Study the Theory of Computation? 2
1.1 The Shelf Life of Programming Tools 2
1.2 Applications of the Theory Are Everywhere 5
2 Languages and Strings 8
2.1 Strings 8
2.2 languages 10
Exercises19
3 The Big Picture: A Language Hierarchy 21
3.1 Defining the Task:LanguageRecognition 21
3.2 The Power of Encoding 22
3.3 A Machine-BasedHierarchyof language Classes28
3.4 A Tractability Hierarchyof language Classes34
Exercises34
4 Computation 36
4.1 DecisionProcedures36
4.2 Determinism and Nondeterminism 41
4.3 Functionson Languagesand Programs 48
ExercisesS2
PART II: FINITE STATEMACHINES AND REGULAR
LANGUAGES 53
5 Finite State Machines 54
5.1 Deterministic Finite State Machines 56
S.2 The Regularlanguages 60
5.3 DesigningDeterministic Finite State Machines 63
iii
iv Contents
5.4 Nondeterministic FSMs 66
5.5 From FSMsto Operational Systems 79
5.6 Simulators for FSMs. 80
5.7 Minimizing FSMs. 82
5.8 A Canonical Form for Regular languages 94
5.9 Finite State Transducers. 96
5.10 Bidirectional Transducers. 98
5.11 Stochastic Finite Automata: Markov Models and HMMs. 101
5.12 Finite Automata, Infinite Strings: BOchiAutomata. 115
Exercises 121
6 Regular Expressions 127
6.1 What is a Regular Expression? 128
6.2 Kleene's Theorem 133
6.3 Applications of Regular Expressions 147
6.4 Manipulating and Simplifying Regular Expressions 149
Exercises151
7 Regular Grammars. 155
7.1 Definition of a Regular Grammar 155
7.2 Regular Grammars and Regular Languages 157
Exercises 161
8 Regular and Nonregular Languages 162
8.1 How Many Regular languages Are There? 162
8.2 Showing That a language Is Regular 163
8.3 Some Important Closure Properties of Regular languages 165
8.4 Showing That a language is Not Regular 169
8.5 ExplOiting Problem-Specific Knowledge 178
8.6 Functions on Regular languages 179
Exercises 182
9 Algorithms and Decision Procedures for Regular
Languages 187
9.1 Fundamental Decision Procedures 187
9.2 Summary of Algorithms and Decision Procedures for Regular Languages 194
Exercises 196
10 Summary and References 198
References 199
Contents v
PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN
AUTOMATA 201
11 Context-Free Grammars 203
11.1 Introduction to Rewrite Systems and Grammars 203
11.2 Context-Free Grammars and Languages 207
11.3 Designing Context-Free Grammars 212
11.4 Simplifying Context-Free Grammars. 212
11.5 Proving That a Grammar is Correct. 215
11.6 Derivations and ParseTrees 218
11.7 Ambiguity 220
11.8 Normal Forms. 232
11.9 Island Grammars. 241
11.10 Stochastic Context-Free Grammars. 243
Exercises 245
12 Pushdown Automata 249
12.1 Definition of a (Nondeterministic) PDA 249
12.2 Deterministic and Nondeterministic PDAs 254
12.3 Equivalence of Context-Free Grammars and PDAs 260
12.4 Nondeterminism and Halting 274
12.5 Alternative Equivalent Definitions of a PDA. 275
12.6 Alternatives that are Not Equivalent to the PDA. 277
Exercises 277
13 Context-Free and Noncontext-Free Languages 279
13.1 Where Do the Context-Free Languages Fit in the Big Picture? 279
13.2 Showing That a language is Context-Free 280
13.3 The Pumping Theorem for Context-Free Languages 281
13.4 Some Important Closure Properties of Context-Free languages 288
13.5 Deterministic Context-Free languages. 295
13.6 Ogden's Lemma. 303
13.7 Parikh's Theorem. 306
13.8 Functions on Context-Free Languages. 308
Exercises 310
14 Algorithms and Decision Procedures for Context-Free
Languages 314
14.1 The Decidable Question.s 314
14.2 The Undecidable Questions 320
PAR T
INTRODUCTION
1
CHAPTER 1
Why Study the Theory
of Computation?
n this book, we present a theory of what can he computed and what cannot. We also
I sketch some theoretical frameworks that can inform the design of programs to solve
a wide variety of problems. But why do we bother? We don't we just skip ahead and
write the programs that we need? This chapter is a short attempt to answer that question.
1.1 The Shelf Life of Programming Tools
Implementations come and go. In the somewhat early days of computing, program-
ming meant knowing how to write code like:'
ENTRY SXA 4,RETURN
LOQ X
FMP A
FAD a
XCA
FMP X
FAD C
STO RESULT
RETURN TRA 0
A ass 1
a ass 1
c ass 1
x ass 1
TEMP ass 1
STORE ass 1
END
IThis program W36 written Cur the IRM 70Q0.ll computes the vaJUI: oC a 5imph: '4Ua\Jr3Iic ar ~ bs ... c,
2
1.1 The Shelf Life of ProgrammingTools 3
In 1957. Fortran appeared and made it possible for people to write programs that looked
more straightforwardly like mathematics. By 1970. the IBM 360 series of computers was
in widespread use for both business and scientific computing. To submit a job, one keyed
onto punch cards a set of commands in OS/360 JeL (Job Control Language). Guruhood
attached to people who actuaUy knew what something like this meant.'
IIMYJOB JOB (COMPRESS),'VOLKER BANDKE', CLAss.P,COND-(O,NE)
/IBACKUP EXEC PGM=IEBCOPY
IlsysPRINT DO sysOUT-*
/ISYSUTl DO OIsP=sHR,OsN=MY.IMPORTNT.POs
/lsYSUT2 DO OISP=(,CATLG),OSN-MY.IMPORTNT.POS.BACKUP,
II UNIT-33S0,VOL=SER~DISK01,
II OCB=MY.IMPORTNT.POS,SPACE-(CYL,(lO,10,20»
IICOMPREsS EXEC PGM-IEBCOPY
IISYSPRINT DO SYSOUT=~
IIMYPDS DO OISP=OLD,DsN=~.BACKUP.SysUT1
/ISysIN DO·
COPY INDO-MYPOs,OUTDD=MYPDS
IIDELETE2 EXEC PGM=IEFBR14
/IBACKPDs DO OISP=(OLO,OELETE,OELETE),DSN=MY.IMPORTNT.PDS.8ACKUP
By the tum of the millennium. gurus were different. They listened to different music and
had never touched a keypunch machine. But many of them did know that the following
Java method (when compiled with the appropriate libraries) allows the user to select a
file. which is read in and parsed using whitespace delimiters. From the parsed file, the
program builds a frequency map. which shows how often each word occurs in the me:
public static TreeMap<String, Integer> create() throws IOExcept;on
public static TreeMap<string, Integer> create() throws
IOException
{ Integer freq;
String word;
TreeMap<string, Integer> result - new TreeMap<String, Integer>()i
JFileChooser c = new JFileChooser();
int retval - c.showOpenlOialog(null);
if (retval == JFileChooser.APPROVE_OPTION)
{ Scanner s = new Scanner( c.getSelectedFile(»;
while( s.hasNext() )
{ word = s.next().toLowerCase();
freq = result.get(word);
result.put (word, (freq -- null? 1 freq + l))i
}
}
return result;
}
}
21t safely reorganlzes and compresses It partitioned dataset.
4. Chapter 1 Why S~udythe Theory of Computation?
Along the way, other programming languages became popular, at least within some
circles. There was a time when some people bragged that they could write code
like~ .
cr /V»(+/V)- r /V
Today's programmers can't read code from 50 years ago. Programmers from the early
days could never have imagined what a program of today would look like. In the face
of that kind of change, what does it mean to learn the science of computing?
The answer is that there are mathematical properties, both of problems and of
algorithms for solving problems.that depend on neither the details of today's technol-
ogy nor the programming fashion du [our. TIle theory that we will present in this book
addresses some of those properties. Most of what we will discuss was known hy the
early 197()s (barely the middle ages of computing history). But it is still useful in two
key ways:
• It provides a set of abstract structures that are useful for solving certain classes of
problems. These abstract structures can be implemented on whatever hardware/
software platform is available ..
• It defines provable limits to what can be computed, regardless of processor speed
or memory size. An understanding of these limits helps us to focus our design effort
in areas in which it can payoff, rather than on the computing equivalent of the
search for a perpetual motion machine.
In this book our focus will be on analyzing problems, rather than on comparing solu-
tions to problems. We will, of course, spend a lot of time solving problems. But our goal
will be to discover fundamental properties of the problems themselves:
• Is there any computational solution to the problem? 1f not. is there a restricted but
useful variation of the problem for which a solution does exist?
• If a solution exists, can it be implemented using some fixed amount of memory?
• If a solution exists. how efficient is it? More specifically. how do its time and space
requirements grow as the size of the problem grows'?
• Are there groups of problems that are equivalent in the sense that if there is an ef-
ficient solution to one member of the group there is an efficient solution to all the
others'?
"An expression in the programming language APL Q.1t returns t if the largest value in a three clement vee-
tor is greater Ihan ihe sum of the other two elements. and (I otherwise [Gillman nnLlRose 19K4.p. 32111. AI.
though APL is not one or the major progrumming languages in usc lOWlY. its inventor. Kenneth Iverson,
received the 1979 Turing Awtlr~ tor its development.
t.2 Applications of the Theory Are Everywhere 5
1.2 Applications of the Theory Are Everywhere
computers have revolutionized our world. They have changed the course of our daily
lives.the way we do science, the way we entertain ourselves, the way that business is
conducted, and the way we protect our security. The theory that we present in this
book has applications in all of those areas. Throughout the main text. you will find
notes that point to the more substantive application-focused discussions that appear in
Appendices G-Q. Some of the applications that we'll consider are:
• Languages. the focus of this book. enable both machine/machine and person/ma-
chine communication. Without them, none of today's applications of computing
could exist.
Network communication protocols are languages. (I. 1) Most web pages are
described using the Hypertext Markup Language. HTML. (Q.1.2) The Se-
mantic Web.whose goal is to support intelligent agents working on the Web,
exploits additional layers of languages, such as RDF and OWL. that can be
used to describe the content of the Web. (J. 3) Music can be viewed as a lan-
guage. and specialized languages enable composers to create new electronic
music. (N.l) Even very unlanguage-like things. such as sets of pictures, can
be viewed as languages by, for example, associating each picture with the
program that drew it. (0.1.3)
• Both the design and the implementation of modern programming languages rely
heavily on the theory of context-free languages that we will present in Part III. Con-
text-free grammars are used to document the languages' syntax and they form the
basis ror the parsing techniques that all compilers use.
The use or context-free grammars to define programming languages and to
build their compilers is described in Appendix G.
• People use natural languages, such as English. to communicate with each other.
Since the advent of word processing. and then the Internet, we now type or speak
our words to computers. So we would like to build programs to manage our words,
check our grammar, search the World Wide Web, and translate (rom one language
to another. Programs to do thal also rely on the theory of context-free languages
that we present in Part Ill.
A sketch of some of the main techniques used in natural language process-
ing can be found in Appendix L.
• Systems as diverse as parity checkers, vending machines. communication protocols,
and building security devices can be straightforwardly described as finite state ma-
chines, which we'll describe in Chapter 5.
6 Chapter 1 Why Study the Theory of Computation'?
A vending machine is described in Example 5.1. A family of network com-
munication protocols is modeled as finite slate machines in 1.1. An example
of a simple building security system. modeled as a finite state machine, can he
found in J.1. An example of a finite state controller for a soccer-playing robot
can be found in P.4.
• Many interactive video games are (large, often nondeterministic) finite state
machines.
~lIIpl<
l_!a~an
of the use of a finite state machine
be found in N.3.1.
1O describe a role P),,:g I
• DNA is the language of life. DNA molecules. as well as the proteins that they de-
scribe, are strings that are made up of symbols drawn from small alphabets (nu-
cleotides and amino acids, respectively). So computational biologists exploit many
of the same tools that computational linguists use. for example. they rely on tech-
niques that are based on both finite state machines and context-free grammars.
for a very brief introduction to computational biology sec Appendix K. J
• Security is perhaps the most important property of many computer systems. The
undecidability results thai we present in Part IV show that there cannot exist a gen-
eral purpose method for automatically verifying arbitrary security properties of
programs. The complexity results that we present in Part V serve as the basis for
powerful encryption techniques.
For a proof of the undecidability of the correctness of a very simple security
model, see J.2. For a short introduction to cryptography. see J.3.
• Artificial intelligence programs solve problems in task domains ranging from medical
diagnosis to factory scheduling. Various logical frameworks have been proposed for
representing and reasoning with the knowledge that such programs exploit. The un-
decidability results that we present in Part IV show that there cannot exist a general
theorem prover that can decide. given an arbitrary statement in first order logic,
whether or not that statement follows from the system's axioms.The complexity results
that we present in Part V show that. if we back off to the far less expressive system of
Boolean (propositional) logic,while it becomes possible to decide the validity nf a given
statement, it is not possible to do so, in general. in a reasonahle amount of time.
For a discussion of the role of undecidability and complexity results in arti-
ficial intelligence, see Appendix M. The same issues plague the develop-
ment of the Semantic Web. (13)
1.2 Applications of the Theory Are Everywhere 7
• Clearly documented and widely accepted standards play a pivotal role in modem
computing systems.Getting a diverse group of users to agree on a single standard is
never easy. But the undecidability and complexity results that we present in Parts IV
and V mean that, for some important problems, there is no single right answer for all
uses. Expressively weak standard languages may be tractable and decidable, but they
may simply be inadequate for some tasks. For those tasks,expressively powerful lan-
guages. that give up some degree of tractability and possibly decidability, may be re-
quired. The provable lack of a one-size-fits-allianguage makes the standards process
even more difficult and may require standards that allow alternatives.
We'll see one example of this aspect of the standards process when we con-
sider, in 1.3,the design of a description language for the Semantic Web.
• Many natural structures. including ones as different as organic molecules and com-
puter networks.can be modeled as graphs. The theory of complexity that we present
in Part V tells us that, while there exist efficient algorithms for answering some im-
portant questions about graphs, other questions are "hard", in the sense that no ef-
ficient algorithm for them is known nor is one likely to be developed.
We'll discuss the role of graph algorithms in network analysis in 1.2.
• The complexity results that we present in Part V contain a lot of bad news. There
are problems that matter yet for which no efficient algorithm is likely ever to be
found. But practical solutions to some of these problems exist.They rely on a vari-
ety of approximation techniques that work pretty well most of the time.
An almost optimal solution to an instance of the traveling salesman prob-
lem with 1.904,711 cities has been found, as we'll see in Section 27.1. Ran-
domized algorithms can find prime numbers efficiently, as we'll see in
Section 30.2.4. Heuristic search algorithms find paths in computer games
(N.3.2) and move sequences for champion chess-playing programs. (N.2.5)
