## 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