Learntofish's Blog

A blog about math, physics and computer science

Good Books on Formal Languages and Computation

Posted by Ed on October 4, 2010

One part of theoretical computer science deals with formal languages and complexity theory. Formal languages is important for understanding how compilers work, for example if you program in Java the compiler must be able to tell whether your code is correct. For these topics I can recommend the following books:

1. Introduction to the Theory of Computation (by Michael Sipser)
This book has very good ratings on amazon and is indeed nice. I particularly like the chapter on Turing machines. You will quickly get an intuitive understanding. It also has nice little pictures, e.g. one picture illustrates how a multitape Turing machine can be simulated by a single tape Turing machine.

2. Automata and Computability (Undergraduate Texts in Computer Science) (by Dexter C. Kozen)
Kozen starts with automatons and fortunately very easy examples. I like how he explains a nondeterministic automaton by using pebbles. The book also  has a chapter on the Myhill-Nerode relation, a topic I haven’t found elsewhere. You’ll quickly get the meaning of different languages, e.g. Kozen explains that a context free language can be produced by a context free grammar but also can be recognized by a push-down automaton. And as a sort of bonus it contains a chapter on Lambda calculus.

Update (November 07, 2010):
Shai Simonson gave excellent lectures on the “Theory of Computation” at the ArsDigita University (ADU). His lectures are published under the Creative Commons Attribution-ShareAlike license. The videos are also on youtube.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: