Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Introduction to Automata Theory, Languages and Computation

by clemburg (Curate)
on Oct 10, 2001 at 18:55 UTC ( [id://118000]=bookreview: print w/replies, xml ) Need Help??
Order Introduction to Automata Theory, Languages and Computation

Item Description: Theory Book

Review Synopsis: This book is a very good introduction to the theoretical background of languages and computation.

Update: This is a review on "a new edition of the Hopcroft/Ullman classic" (hsmyers) (the second edition, to be precise, with a new coauthor). Authors are: John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.

This book is a very good introduction to the theoretical background of languages and computation.

Topics include:

  • introduction to mathematical proofs: one chapter that introduces notation and methods
  • finite automata (DFA, NFA), regular expressions and regular languages: three chapters on all the theory, with applications to UNIX regexes and a good chapter on algebraic laws for regexes (read: how can we transform a regex)
  • pushdown automata and context-free languages: three chapters on all the theory, with applications to YACC and XML
  • turing machines and undecidability: two chapters, very good and easy-to-follow style
  • intractable problems and additional classes of problems: detailed discussion of problem classification and classes of problems

The style of the book is very application-oriented, with lots of examples and illustrations of the formal results presented. Mathematical notation is very well introduced and explained. Informal, intuitive sketches of proofs are followed by more formal proofs.

All in all, this was a very motivating reading for me. For all those that, like me, lack the theoretical foundation that is laid in the standard computer science courses, this is a good book to read.

The one drawback of this book is the relatively large errata list (seven pages (printed from browser) as of now, be sure to get it from the website before you start reading). IMHO, this number of errors is hard to excuse given the price tag on the book. OTOH, Mr Ullman is quickly responding to error reports, and includes new errors in the errata promptly, so this should not hamper your learning.

Replies are listed 'Best First'.
Re: Introduction to Automata Theory, Languages and Computation
by Dominus (Parson) on Oct 10, 2001 at 23:53 UTC
    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

      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

        Thanks a lot for elaborating on the changes between the first and second editions. Your cites from the introduction are especially helpful to me.

        I will certainly take a look at the new edition.

        --
        Mark Dominus
        Perl Paraphernalia

Re: Introduction to Automata Theory, Languages and Computation
by hsmyers (Canon) on Oct 10, 2001 at 22:29 UTC
    If you had said a new edition of the Hopcroft/Ullman classic somewhere close to the top of the review it might have been better. Not everyone who reads this is going to recognize just “Mr. Ullman” so it would be nice to have the Author/s information just after the title.

    Nice review, it's good to see someone enjoying the book they're reading— even better to share the “why” with the rest of us.

    hsm
Re: Introduction to Automata Theory, Languages and Computation
by George_Sherston (Vicar) on Oct 11, 2001 at 00:48 UTC
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: bookreview [id://118000]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (5)
As of 2024-03-29 06:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found