Reddit reviews Introduction to Automata Theory, Languages, and Computation (3rd Edition)

Always liked Introduction to Automata Theory, Languages, and Computation by Hopcroft and Ullman as an intro text. Undergraduate-level but good treatment of TCS.

If that's too basic, I recommend Theory of Computation by Kozen. It's roughly 1st-year graduate level, intended for those already with some background.

If that's too basic, for a research-level survey of TCS, take a look at Wigderson's Mathematics and Computation.

I'm partial to Hopcroft and Ullman. I'm usually not the "open a book, read the explanations..." type of learner but Hopcroft&Ullman is very clear and concise, so I found myself doing just that. No need to skip ahead to figure out the point of it all, they just explain it in logical order. This text goes quite a bit deeper than most algorithms courses will go but it's a great way to pump iron with your brain and everything you learn will be applicable to whatever curriculum is taught in your algorithms course.

TTFP. I would rank SICP, TTFP, then Ullman/Hopcroft as a sort of nice set of introductions to formal language theory and computation. SICP being the closest to programming, and Ullman/Hopcroft being the furthest. TTFP is a nice "in between".

Introduction to Automata Theory, Languages, and Computation is the standard text. Jeff Ullman has a page for the book, and has taught the subject a couple of times on Coursera.

Hey don't underestimate the theoretical side of computer science, how about answering the age old question [What are the fundamental capabilities and limitations of computers?] (http://www.amazon.in/Introduction-Automata-Theory-Languages-Computation/dp/0321455363) or how about [ design and workings of computers and software] (http://www.goodreads.com/book/show/44882.Code)

Thanks, I already have a book on this I was planning on reading: Introduction to Automata Theory, Languages, and Computation. I just started reading CLRS though, do you think it would be helpful to finish it or are the two mostly unrelated?

I studied from Introduction to Automata, Languages, and Computation, and used their definitions here :)

Certainly one can define FSMs to always have two tapes, and just not use the output one.

Here's a PDF which I used as reference and which covers most concepts:

https://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf

​

For more depth, this book is often seen as "the bible" of this topic:

https://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455363

​

If you're looking for exercises, this could be a good resource (especially designing Turing Machines is a thing of practice):

https://www.cl.cam.ac.uk/teaching/exams/pastpapers/t-ComputationTheory.html

​

If primitive recursive functions are also relevant for you, I can strongly recommend this video to you:

https://www.youtube.com/watch?v=cjq0X-vfvYY