Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Can you talk about how this new edition differs from the old edition?

I have a copy of the first edition of this book, and I've always thought it was one of the worst computer science texts I'd ever read. I found it turgid and confusing. The arguments are all overformalized, with excessive notation that obscures what's really going on. You say that the formal proofs are preceded by informal sketches, and I hope that's true, because they sure didn't do it in the first edition. For example, I know from experience that many people are deeply confused by the first edition's explanation of the pumping lemma for regular languages. But I also know that there's nothing hard about the pumping lemma, because I've been able to teach high school students about it in half an hour. This isn't a boast, because I think anyone could do the same. But the first edition of this book didn't do it.

The first edition's treatment of NP-completeness is similarly turgid. They use nonstandard terminology and nonstandard definitions (which I hope they cleaned up for the new edition), but that isn't my real complaint. My real complaint is that even I already know all about everything they're going to say about NP-completeness, I can't understand their discussion. It's just too convoluted. (I'd invite interested readers to compare the treatment in the Hopcroft and Ullman book with the treatment in Garey and Johnson. I did this and found it educational as an example of how to write a good technical paper.)

You also said that "The style of the book is vey application-oriented." That would be a welcome change from the first edition, but I wish you had given an example, because I'm skeptical. On page 57 of the first edition is a section titled "Applications of the pumping lemma." The section contains a detailed secription of how to construct a pumping lemma proof that a language is not regular. What language? No language in particular. The title notwithstanding, the promised application is nowhere to be found. Earlier, on page 46, there is a paragraph about the use of regular expressions in the unix text editor. It's really too little. More than once I've been asked by CS students what this finite automaton nonsense was good for, and they were shocked when I said "Oh, that's how 'grep' works." The book doesn't tell you and it doesn't get close to communicating any of the important uses of regular expressions. It looks like section 3.3 of the new edition may remedy this, but I can't tell.

Anyway, I'm glad you liked the new edition, and if what you say is true, I guess the authors have learned something since 1979, when the first edition appeared. The book's web page does say that it "features more explanations and intuition, more applications, and a selection of topics with an eye toward balancing the need for relevance with the need to master the foundations of computer science." So I suppose from this that I'm not the only person who had big complaints about the first edition. But I wish you had been able to compare the new edition with the first edition, and I'd be reluctant to buy the new version without taking a very close look over some of the material to make sure it really had been improved.

Mark Dominus
Perl Paraphernalia

In reply to Re: Introduction to Automata Theory, Languages and Computation by Dominus
in thread Introduction to Automata Theory, Languages and Computation by clemburg

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (2)
As of 2023-11-29 05:23 GMT
Find Nodes?
    Voting Booth?

    No recent polls found