Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

comment on

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

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.

In reply to 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? | Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2022-12-05 18:49 GMT
Find Nodes?
    Voting Booth?

    No recent polls found