Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Can you talk about how this new edition differs from the old edition?

Sure, no problem. I don't own the old edition, but I have heard enough bad comments that I feel I can comment on the new one.

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.

This has profoundly changed, I'd say. The new book comes nowhere close to being "one of the worst". The topic of the book will not appeal to all people, but the coverage of the material is clear and easy to understand. Please note again that I have no formal background in mathematics (I originally have studied psychology and brain research, and statistics is pretty much the only part of higher math I feel somehow educated about). Despite this, I was able to cover a lot of ground in short time, due to the excellent introductory sections in the book.

I found it turgid and confusing. The arguments are all overformalized, with excessive notation that obscures what's really going on.

That has definitively changed. The authors also note in the introduction that they did change this for a number of reasons:

  • back when the first edition was published, automata theory was still in the active research area; today it is "a staple of the undergraduate curriculum" as they put it
  • the old book was intended for graduate students, while the new book is intended for use in the undergraduate curriculum
  • since computer science has grown so large, automata theory can today occupy only a limited space in a curriculum
  • "Fourthly, CS has become a more vocational subject, and there is a severe pragmatism among many of its students."

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.

Oh yes, it's true. Just take a look at the book in your nearest library.

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 pumping lemma took me about half an hour to cover, mostly because there is a missing assumption in the proof (the language must have no bound on the length of its members, meaning it is infinite, for the pumping lemma to work). I found the explanation in the book very clear and easy.

The first edition's treatment of NP-completeness is similarly turgid.

Sorry, I can't really comment on this, since I have not yet covered this part of the book. I am still with Turing machines and undecidability. Maybe next week :-) ...

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.

Take a look at sections 2.1 (using a finite automaton to validate a simple e-commerce protocol), 3.3 and 3.4 (UNIX Regexes and Algebraic Laws for Regular Expressions) and 5.3 (YACC and XML as applications of context free grammars). That pretty much explains what I mean. OK, maybe I should have said "The book is written with an eye towards possible applications of the theoretical material covered." and not "very application oriented". The latter may convey a wrong message.

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.

Indeed I think they have.

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.

I'd do so, too, if I were you. It is hard to believe a book can change so much. OTOH, I *really* like this text. It opened up the world of a big part of "classic" formal computer science for me. That is no little thing. Maybe I am just too excited about the book, but I still think it is definitively worth a look on the next trip to the library or bookstore.

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com


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

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



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    [karlgoethebier]: he,he! literally it's "Fleischraum"
    erix .oO( note to self: running 100 syncing database instances on a single machine is hard on the hard disks )
    [1nickt]: Oh, no, sins of the flesh were *especially* verboten at that monastery!

    How do I use this? | Other CB clients
    Other Users?
    Others having an uproarious good time at the Monastery: (5)
    As of 2017-12-13 13:21 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      What programming language do you hate the most?




















      Results (367 votes). Check out past polls.

      Notices?