自动机理论、语言与计算导论第三版

5星 · 超过95%的资源需积分: 44 81 浏览量更新于2024-07-22 11 收藏 5.67MB PDF 举报

"Introduction To Automata Theory, Languages, And Computation 3rd Edition" 是一本关于自动机理论、语言和计算的教科书，由John E. Hopcroft、Rajeev Motwani 和 Jeffrey D. Ullman三位教授合著，是Coursera上关于automata课程的推荐教材，目前已更新至第三版。正文: 自动机理论是计算机科学的一个核心领域，主要研究抽象计算设备的性质、行为和能力。这本书深入浅出地介绍了这个领域的基本概念，包括有限状态自动机（Finite State Machines）、图灵机（Turing Machines）以及形式语言（Formal Languages）等概念。 1. **有限状态自动机**：这是自动机理论的基础，它是一个具有有限数量状态的计算模型，可以用来识别或接受特定的字符串集。书中可能详细讨论了确定性有限自动机（Deterministic Finite Automata, DFA）和非确定性有限自动机（Non-deterministic Finite Automata, NFA），并分析了它们之间的转换关系和等价性。 2. **图灵机**：图灵机是理论计算机科学的基石，它模拟了人类进行计算的能力。书中的第三版可能会涵盖单带图灵机（Single-Tape Turing Machine）以及如何用它们来定义可计算问题的复杂性。 3. **形式语言**：形式语言是自动机理论中的另一个关键概念，是通过特定规则生成的一组字符串集合。书会介绍正则语言（Regular Languages）、上下文无关语言（Context-Free Languages）和递归可枚举语言（Recursively Enumerable Languages），以及它们对应的文法系统如正则文法、上下文无关文法和上下文敏感文法。 4. **计算理论**：除了自动机和语言，本书可能还会涉及计算的理论边界，如图灵停机问题（Turing Halting Problem）和计算复杂性理论，这些理论探讨了哪些问题是可解的，哪些是不可解的，以及解决这些问题所需的计算资源。 5. **练习和问题**：书中包含了大量的练习题和问题，这些可能来自于Gradiance Corporation，一家提供在线评估系统的公司。这些问题有助于读者巩固理解，并测试他们在自动机理论和相关计算概念上的掌握程度。 6. **商标和版权**：书中的警告提到了制造商和销售商对产品名称的商标权益，这表明书中在引用实例或例子时尊重了知识产权。通过学习这本书，读者不仅可以了解自动机的基本原理，还能掌握如何应用这些原理来解决实际的计算问题，对于计算机科学、软件工程和理论计算机科学的学生和研究人员来说，是一本不可多得的参考资料。

TABLE OF CONTENTS

xvii

11.5.6 Exercises for Section 11.5 . . . . . . . . . . . . . . . . . . 521

11.6 Summary of Chapter 11 . . . . . . . . . . . . . . . . . . . . . . . 522

11.7 Gradiance Problems for Chapter 11 . . . . . . . . . . . . . . . . . 523

11.8 References for Chapter 11 . . . . . . . . . . . . . . . . . . . . . . 524

Index 527

Chapter 1

Automata: The Metho ds

and the Madness

Automata theory is the study of abstract computing devices, or \machines."

Before there were computers, in the 1930's, A. Turing studied an abstract ma-

chine that had all the capabilities of to day's computers, at least as far as in

what they could compute. Turing's goal was to describ e precisely the b oundary

between what a computing machine could do and what it could not do his

conclusions apply not only to his abstract

Turing machines

, but to to day's real

machines.

In the 1940's and 1950's, simpler kinds of machines, which we today call

\nite automata," were studied byanumber of researchers. These automata,

originally prop osed to mo del brain function, turned out to be extremely useful

for a variety of other purp oses, whichwe shall mention in Section 1.1. Also in

the late 1950's, the linguist N. Chomsky b egan the study of formal \grammars."

While not strictly machines, these grammars have close relationships to abstract

automata and servetoday as the basis of some imp ortant software comp onents,

including parts of compilers.

In 1969, S. Co ok extended Turing's study of what could and what could

not be computed. Co ok was able to separate those problems that can b e solved

eciently by computer from those problems that can in principle b e solved, but

in practice takesomuch time that computers are useless for all but very small

instances of the problem. The latter class of problems is called \intractable,"

or \NP-hard." It is highly unlikely that even the exp onential improvementin

computing speed that computer hardware has been following (\Mo ore's Law")

will have signicant impact on our abilitytosolve large instances of intractable

problems.

All of these theoretical developments b ear directly on what computer scien-

tists do to day. Some of the concepts, like nite automata and certain kinds of

formal grammars, are used in the design and construction of important kinds

of software. Other concepts, likethe Turing machine, help us understand what

CHAPTER 1. AUTOMATA: THE METHODS AND THE MADNESS

we can exp ect from our software. Esp ecially, the theory of intractable problems

lets us deduce whether we are likely to b e able to meet a problem \head-on"

and write a program to solve it (because it is not in the intractable class), or

whether we have to nd some way to work around the intractable problem:

ndanapproximation, use a heuristic, or use some other metho d to limit the

amount of time the program will sp end solving the problem.

In this introductory chapter, we b egin with a very high-level view of what

automata theory is about, and what its uses are. Much of the chapter is de-

voted to a survey of pro of techniques and tricks for discovering proofs. Wecover

deductive proofs, reformulating statements, proofs by contradiction, proofs by

induction, and other imp ortant concepts. A nal section introduces the con-

cepts that pervade automata theory: alphab ets, strings, and languages.

1.1 Why Study Automata

Theory?

There are several reasons why the study of automata and complexity is an

important part of the core of Computer Science. This section serves to introduce

the reader to the principal motivation and also outlines the ma jor topics covered

in this bo ok.

1.1.1 Intro duction to Finite Automata

Finite automata are a useful mo del for many important kinds of hardware and

software. We shall see, starting in Chapter 2, examples of how the concepts are

used. For the moment, let us just list some of the most imp ortant kinds:

1. Software for designing and checking the b ehavior of digital circuits.

2. The \lexical analyzer" of a typical compiler, that is, the compiler com-

ponent that breaks the input text into logical units, such as identiers,

keywords, and punctuation.

3. Software for scanning large bodies of text, such as collections of Web

pages, to nd o ccurrences of words, phrases, or other patterns.

4. Software for verifying systems of all types that have a nite number of

distinct states, such as communications proto cols or proto cols for secure

exchange of information.

While we shall soon meet a precise denition of automata of various types,

let us b egin our informal introduction with a sketch of what a nite automaton

is and does. There are many systems or comp onents, such as those enumerated

above, that may be viewed as b eing at all times in one of a nite number

of \states." The purp ose of a state is to remember the relevant portion of the

system's history. Since there are only a nite numb er of states, the entire history

generally cannot be remembered, so the system must be designed carefully,to

1.1. WHY STUDYAUTOMATA THEORY?

remember what is important and forget what is not. The advantage of having

only a nite number of states is that we can implement the system with a xed

set of resources. For example, we could implement it in hardware as a circuit, or

as a simple form of program that can make decisions looking only at a limited

amount of data or using the p osition in the co de itself to make the decision.

Example 1.1 :

Perhaps the simplest nontrivial nite automaton is an on/o

switch. The device remembers whether it is in the \on" state or the \o " state,

and it allows the user to press a button whose eect is dierent, depending on

the state of the switch. That is, if the switch is in the o state, then pressing

the button changes it to the on state, and if the switch is in the on state, then

pressing the same button turns it to the o state.

Push

Start

onoff

Figure 1.1: A nite automaton modeling an on/o switch

The nite-automaton mo del for the switchis shown in Fig. 1.1. As for all

nite automata, the states are represented by circles in this example, wehave

named the states

and

o

. Arcs b etween states are lab eled by \inputs," which

represent external inuences on the system. Here, both arcs are labeled bythe

input

Push

, which represents a user pushing the button. The intent of the two

arcs is that whichever state the system is in, when the

Push

input is received

it goes to the other state.

One of the states is designated the \start state," the state in which the

system is placed initially. In our example, the start state is

o

,andweconven-

tionally indicate the start state by the word

Start

and an arrow leading to that

state.

It is often necessary to indicate one or more states as \nal" or \accepting"

states. Entering one of these states after a sequence of inputs indicates that

the input sequence is go o d in some way. For instance, we could have regarded

the state

in Fig. 1.1 as accepting, because in that state, the device being

controlled by the switch will operate. It is conventional to designate accepting

states by a double circle, although wehave not made anysuch designation in

Fig. 1.1.

Example 1.2 :

Sometimes, what is remembered by a state can be muchmore

complex than an on/o choice. Figure 1.2 shows another nite automaton that

could b e part of a lexical analyzer. The job of this automaton is to recognize

the keyword

then

. It thus needs ve states, each of which represents a dierent

CHAPTER 1. AUTOMATA: THE METHODS AND THE MADNESS

position in the word

then

that has been reached so far. These p ositions corre-

spond to the prexes of the word, ranging from the empty string (i.e., nothing

of the word has been seen so far) to the complete word.

t th the

Start tnhe

then

Figure 1.2: A nite automaton modeling recognition of

then

In Fig. 1.2, the ve states are named by the prex of

then

seen so far. Inputs

correspond to letters. Wemay imagine that the lexical analyzer examines one

character of the program that it is compiling at a time, and the next character

to b e examined is the input to the automaton. The start state corresponds to

the empty string, and each state has a transition on the next letter of

then

the state that corresp onds to the next-larger prex. The state named

then

entered when the input has spelled the word

then

. Since it is the job of this

automaton to recognize when

then

hasbeenseen,we could consider that state

the lone accepting state.

1.1.2 Structural Representations

There are two imp ortant notations that are not automaton-like, but play an

important role in the study of automata and their applications.

Grammars

are useful mo dels when designing software that pro cesses data

with a recursive structure. The b est-known example is a \parser," the

component of a compiler that deals with the recursively nested features

of the typical programming language, such as expressions | arithmetic,

conditional, and so on. For instance, a grammatical rule like

)

states that an expression can be formed by taking any two expressions

and connecting them by a plus sign this rule is typical of how expressions

of real programming languages are formed. We introduce context-free

grammars, as they are usually called, in Chapter 5.

Regular Expressions

also denote the structure of data, esp ecially text

strings. As we shall see in Chapter 3, the patterns of strings they describ e

are exactly the same as what can be described by nite automata. The

style of these expressions diers signicantly from that of grammars, and

we shall content ourselves with a simple example here. The UNIX-style

regular expression

'A-Z]a-z]* ]A-Z]A-Z]'

represents capitalized

words followed byaspace and two capital letters. This expression rep-

resents patterns in text that could b e a city and state, e.g.,

Ithaca NY

It misses multiword city names, such as

Palo Alto CA

,which could be

captured by the more complex expression

'A-Z]a-z]*( ]A-Z]a-z]*)* ]A-Z]A-Z]'

剩余549页未读，继续阅读

wz619899442

粉丝: 0
资源: 2

自动机理论、语言与计算导论第三版

Introduction to Automata Theory, Languages, and Computation Solutions

Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation(Second Edition)中文答案

《自动机理论、语言和计算导论》 + 课后习题答案（全）

Introduction To Automata Theory.zip

Introduction.to.Automata.Theory,.Languages,.and.Computation

switching and finite automata theory习题答案

Intro to Automata Theory, Languages and Computation

Introduction to Automata Theory Languages and Computation

Introduction to Automata Theory

最新资源