Introduction to the Theory of Computation

Michael Sipser

Mentioned 12

This highly anticipated revision builds upon the strengths of the previous edition. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. Important Notice: Media content referenced within the product description or the product text may not be available in the ebook version.

More on Amazon.com

Mentioned in questions and answers.

What concepts in Computer Science do you think have made you a better programmer?

My degree was in Mechanical Engineering so having ended up as a programmer, I'm a bit lacking in the basics. There are a few standard CS concepts which I've learnt recently that have given me a much deeper understanding of what I'm doing, specifically:

Language Features

  • Pointers & Recursion (Thanks Joel!)

Data Structures

  • Linked Lists
  • Hashtables

Algorithms

  • Bubble Sorts

Obviously, the list is a little short at the moment so I was hoping for suggestions as to:

  1. What concepts I should understand,
  2. Any good resources for properly understanding them (as Wikipedia can be a bit dense and academic sometimes).

I find it a little funny that you're looking for computer science subjects, but find wikipedia too academic :D

Anyway, here goes, in no particular order:

As a recent graduate from a computer science degree I'd recommend the following:

Some of the OS concepts

 ( memory, IO, Scheduling, process\Threads, multithreading )

[a good book "Modern Operating Systems, 2nd Edition, Andrew S. Tanenbaum"]

Basic knowledge of Computer networks

[a good book by Tanenbaum

OOPS concepts

Finite autometa

A programming language ( I learnt C first then C++)

Algorithms ( Time\space complexity, sort, search, trees, linked list, stack, queue )

[a good book Introduction to Algorithms]

I've always been a largely independent learner gleaning what I can from Wikipedia and various books. However, I fear that I may have biased my self-education by inadvertent omission of topics and concepts. My goal is to teach myself the equivalent of an undergraduate degree in Computer Science from a top university (doesn't matter which one).

To that end, I've purchased and started reading a few academic textbooks:

As well as a few textbooks I have left over from classes I've taken at a mediocre-at-best state university:

My questions are:

  • What topics aren't covered by this collection?
  • Are there any books that are more rigorous or thorough (or even easier to read) than a book listed here?
  • Are there any books that are a waste of my time?
  • In what order should I read the books?
  • What does an MIT or Stanford (or UCB or CMU ...) undergrad learn that I might miss?

Software engineering books are welcome, but in the context of academic study only please. I'm aware of Code Complete and the Pragmatic Programmer, but I'm looking for a more theoretical approach. Thanks!

I think you can use most of the other books for reference and just absorb Programming Pearls in its entirety. Doing so would make you better than 90% of the programmers I've ever met.

The "Gang of Four" Design Patterns book. The Design Patterns course I took in college was probably the most beneficial class I've ever taken.

First, I wouldn't worry about it. But if you'd like a book to learn some of the abstract CS ideas, I'd recommend The Turing Omnibus or Theoretical Introduction to Programming.

If I were deciding between hiring two programmers and neither had much experience, but one had a CS degree and the other didn't, I'd hire the one with the CS degree. But when you get to comparing two programmers with a dozen years of experience, the degree hardly matters.

Even i'm in the same plane: studying computer science in my free time after work; These are some of the books i have in my shelf right now

  1. Applying UML and patterns - Larman
  2. Introduction to algorithms - Cormen
  3. Discrete mathematics and its applications - Rosen
  4. Software Engineering
  5. Advanced Programming in the UNIX Environment

Will udpate this list further as soon as i finish them... :-)

File Structures: An object oriented approach with C++

A lot of good info about block devices and file structuring which you won't find in any of the books you listed. It got a few critical reviews on Amazon because people didn't like his code examples, but the point of the book is to teach the concepts, not give cut and paste code examples.

Also make sure to get a book on compilers

Biggest two omissions I see:

For operating systems I prefer the Tanenbaum instead of the Silberschatz but both are good:

And about the order, that would depend on your interests. There aren't many prerequisites, automata for compilers is the most obvious one. First read the automata book and then the dragon one.

I don't know all the books you have, but the ones I know are good enough so that may mean the others are decent as well.

You are missing some logic and discrete math books as well.

And let's not forget some database theory books!

Possible Duplicate:
Learning to write a compiler

I looked around trying to find out more about programming language development, but couldn't find a whole lot online. I have found some tutorial videos, but not much for text guides, FAQs, advice etc. I am really curious about how to build my own programming language. It brings me to SO to ask:

How can you go about making your own programming language?

I would like to build a very basic language. I don't plan on having a very good language, nor do I think it will be used by anyone. I simply want to make my own language to learn more about operating systems, programming, and become better at everything.

Where does one start? Building the syntax? Building a compiler? What skills are needed? A lot of assembly and understanding of the operating system? What languages are most compilers and languages built in? I assume C.

I'd say that before you begin you might want to take a look at the Dragon Book and/or Programming Language Pragmatics. That will ground you in the theory of programming languages. The books cover compilation, and interpretation, and will enable you to build all the tools that would be needed to make a basic programming language.

I don't know how much assembly language you know, but unless you're rather comfortable with some dialect of assembly language programming I'd advise you against trying to write a compiler that compiles down to assembly code, as it's quite a bit of a challenge. You mentioned earlier that you're familiar wtih both C and C++, so perhaps you can write a compiler that compiles down to C or C++ and then use gcc/g++ or any other C/C++ compiler to convert the code to a native executable. This is what the Vala programming language does (it converts Vala syntax to C code that uses the GObject library).

As for what you can use to write the compiler, you have a lot of options. You could write it by hand in C or C++, or in order to simplify development you could use a higher level language so that you can focus on the writing of the compiler more than the memory allocations and the such that are needed for working with strings in C.

You could simply generate the grammars and have Flex and Bison generate the parser and lexical analyser. This is really useful as it allows you to do iterative development to quickly work on getting a working compiler.

Another option you have is to use ANTLR to generate your parser, the advantage to this is that you get lots of target languages that ANTLR can compile to. I've never used this but I've heard a lot about it.

Furthermore if you'd like a better grounding on the models that are used so frequently in programming language compiler/scanner/parser construction you should get a book on the Models of Computation. I'd recommend Introduction to the Theory of Computation.

You also seem to show an interest in gaining an understanding of operating systems. This I would say is something that is separate from Programming Language Design, and should be pursued separately. The book Principles of Modern Operating Systems is a pretty good starting place for learning about that. You could start with small projects like creating a shell, or writing a programme that emulates the ls command, and then go into more low level things, depending on how through you are with the system calls in C.

I hope that helps you.

EDIT: I've learnt a lot since I write this answer. I was taking the online course on programming languages that Brown University was offering when I saw this answer featured there. The professor very rightly points out that this answer talks a lot about parsers but is light on just about everything else. I'd really suggest going through the course videos and exercises if you'd like to get a better idea on how to create a programming language.

I am a newbie in the software development field. I am hungry for more avenues through which I can develop, nurture, and mature in my development, scripting, and programming skills, more so outside of work time. I'd like to know what type of set-up (hardware and/or software) would be extremely beneficial or that others have found necessary for this endeavor.

I want to be able to equip my home 'office' with tools that will enable me to progress and grow as a developer.

Write Code:

In this article Jeff Atwood talks about how to become better at designing and writing software by designing and writing a lot of software. His is stated more elegantly, but it is a valid point. The more you do something, the better you will get at it.

Hardware:

Any modern PC/Mac hardware should suffice. If you plan to run Windows or Linux I would use a PC over Mac. There is a lot of clamor over which is better, but use the one you like the best.

It should be a moot point in this day and age, but make sure you have some sort of reliable internet connectivity (cable, dsl, whatever...). Then you will have access to Google and stackoverflow; both good resources for programmers.

Make sure you have a keyboard and mouse which are comfortable to you. This includes setting up your desk and chair to accommodate your height and hand position. You will be at the computer for long stretches of time, and you want to be comfortable.

Editor/IDE:

Choose an editor: Vim, EMACS, KATE, Eclipse, whatever. It doesn't really matter which one, but whichever one you do pick learn it well. The editor is your main tool and you want to be comfortable and knowledgeable when using it. The better you know your editor the faster you can create/edit code.

It helps to have an editor that runs on all platforms you may be developing on, but it is not necessary.

Build Tools:

At some point you will find your self face to face with having to create or fix a build stystem. Make is pretty standard for *nix and C/C++, but for your own personal projects find the one that suits you best. There are a lot to choose from: Scons, Ant, Make, Jam, ...

I personally use SCons, since it is python based, and I like python.

Books:

When learning a new topic I would recommend getting a good book on it. This will generally give you a good overview of what you are getting into, and give you a good foundation to learn from. Google and Stackoverflow are good for specific questions, but a general overview of a topic is harder to get.

This of course assumes you have the luxury of time and money. For the monetarily constrained you can often find free versions of electronic books online.

Languages:

I used to have strong feelings about which languages to learn, but now I realize you should write in the language you enjoy most. However don't be afraid to try new languages. I personally like C++, python, and C# in no particular order.

Since you are just starting out pick the languages which you can get for free, which I actually think is most languages these days.

In the business world the language of choice tends to fluctuate on about a 5-7 year cycle. However you can find a job (at least currently) in all the "big" languages (C++, JAVA, C# VB.net, python, ruby, perl, ...). If you learn one of the modern languages well, it is typically not a problem to transition to another language quickly. The libraries tend to take longer to learn than the language itself. So pick a language you like learning in and learn it.

Miscellaneous Thoughts:

As Marc Charbonneau said set up source control. There are plenty of free source control offerings, so pick the one you like best. Personally I use Perforce, which is free for two or less people. I ahve heard good things about Subversion and git as well. The specific one is not as important, but choose one of them.

If you want to get a deeper knowledge of computing I would recommend Sipser's Book and Knuth.

Whichever language you choose I would spend time learning the debugger for it as well.

If you are doing web development, then make sure you know how to minimally setup and run Apachie (or IIS).

Avoid holy wars if you can. They are a waste of time, and you don't learn anything from it except that people are stubborn. Some Holy war topics (bracket style, editors, endianess, "best" language, "best" OS, ...).

My personal setup:

Standard PC (Windows XP Pro)

  • Visual Studio 2007 (a little behind).
  • VIM
  • Python
  • C/C++
  • C#
  • Scons

Standard PC (FreeBSD runs headless: no GUI)

  • gnu tool chain (Make, C/C++ etc)
  • VIM
  • python
  • Scons

Out of curiosity, I am trying to identify what model of computation a system I work with is functionally equivalent to, and prove the equivalence. The longer I spend on this problem the more I suspect the system isn't Turing-equivalent. My understanding of Turing Machines and recursively enumerable languages is good but I don't know much about automata with lesser capabilities (e.g. pushdown automata), so I am not sure how to proceed.

First, can anyone recommend a good resource for learning about different models of computation? I'm interested in grammars, languages and automata, and how to prove equivalence and difference between all of them. Ideally the resource would break down all the elements of each model in great detail and compare them.

Second, is there a general approach or framework that should be used when trying to fit a system onto any of these computational models?

I'd recommend a good textbook on computer science (In my Uni course, I'm studying from Sipser's Introduction to the Theory of Computation, which is very good in my opinion. You might also find a free textbook which teaches the same, but I don't have any experience with one so I can't recommend).

The other approach would probably be just to read up on Wikipedia. You can actually get a lot of mileage out of the Wikipedia articles, if you know what you're looking for and in what order. Also, if anything is unclear, you can usually Google it and find more resources about that particular subject.

Of course, this will not be as good as a real textbook, but it's a good place to get started right now, and it's free.

As a starting point, I'd recommend reading about the following topics (in the order listed):

  1. Deterministic Finite Automaton
  2. Nondeterministic Finite Automaton, and their equivalence to DFAs.
  3. Regular Languages, and their equivalence to DFAs.
  4. Pushdown Automata
  5. Context-free Grammars, and their equivalence to Pushdown Automata.
  6. Chomsky Hierarchy
  7. Turing Machines

That should provide a very brief introduction to most of the computational models people talk about. 2: I'd recommend a good textbook on computer science (In my Uni course, I'm studying from Sipser's Introduction to the Theory of Computation, which is very good in my opinion). The other approach would probably be just to read up on Wikipedia. You can actually get a lot of mileage out of the Wikipedia articles, if you know what you're looking for and in what order. Also, if anything is unclear, you can usually Google it and find more resources about that particular subject. As a starting place, I'd recommend reading about the following topics (in the order listed): 1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Please suggest me some good books on "Formal languages and Automata Theory".

Thanks!

The book here is Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani and Ullman (Ullman is one of the dragon book guys). (I recommend finding an older edition in your library if you can; the older editions were shorter and I don't see much value in the additional material in the new editions).

Another great book is Introduction to the Theory of Computation by Sipser.

You can not go wrong with one of those two.

I'm developing a software to generate a Turing Machine from a regular expression.

[ EDIT: To clarify, the OP wants to take a regular expression as input, and programmatically generate a Turing Machine to perform the same task. OP is seeking to perform the task of creating a TM from a regular expression, not using a regular expression. ]

First I'll explain a bit what I have done and then what is my specific problem:

I've modeled the regular expression as follows:

RegularExpression (interface): the classes below implements this interface

Simple (ie: "aaa","bbb","abcde"): this is a leaf class it does not have any subexpressions

ComplexWithoutOr (ie: "a(ab)*","(a(ab)c(b))*"): this class contains a list of RegularExpression.

ComplexWithOr (ie: "a(a|b)","(a((ab)|c(b))"): this class contains an Or operation, which contains a list of RegularExpression. It represents the "a|b" part of the first example and the "(ab)|c(b)" of the second one.

Variable (ie: "awcw", where w E {a,b}*): this is not yet implemented, but the idea is to model it as a leaf class with some different logic from Simple. It represents the "w" part of the examples.

It is important that you understand and agree with the model above. If you have questions make a comment, before continue reading...

When it comes to MT generation, I have different levels of complexity:

Simple: this type of expression is already working. Generates a new state for each letter and moves right. If in any state, the letter read is not the expected, it starts a "rollback circuit" that finishes with the MT head in the initial position and stops in a not final state.

ComplexWithoutOr: here it comes my problem. Here, the algorithm generates an MT for each subexpression and concat them. This work for some simple cases, but I have problems with the rollback mechanism.

Here is an example that does not work with my algorithm:

"(ab)abac": this is a ComplexWithoutOr expression that contains a ComplexWithOr expression "(ab)" (that has a Simple expression inside "ab") and a Simple expression "abac"

My algorithm generates first an MT1 for "ab". This MT1 is used by the MT2 for "(ab)*", so if MT1 succeed it enters again in MT1, otherwise MT1 rollbacks and MT2 finishes right. In other words, MT2 cannot fail.

Then, it generates an MT3 for "abac". The output of MT2 it is the input of MT3. The output of MT3 is the result of the execution

Now, let suppose this input string: "abac". As you can see it matches with the regular expression. So let see what happens when the MT is executed.

MT1 is executed right the first time "ab". MT1 fails the second time "ac" and rollback, putting the MT head in the 3rd position "a". MT2 finishes right and input is forwarded to MT3. MT3 fails, because "ac"!="abac". So MT does not recognize "abac".

Do you understand the problem? Do you know any solution for this?

I'm using Java to develop it, but the language it is not important, I'd like to discuss the algorithm.

Michael Sipser, in Introduction to the Theory of Computation, proves in chapter 1 that regular expressions are equivalent to finite automata in their descriptive power. Part of the proof involves constructing a nondeterministic finite automaton (NDFA) that recognizes the language described by a specific regular expression. I'm not about to copy half that chapter, which would be quite hard due to the notation used, so I suggest you borrow or purchase the book (or perhaps a Google search using these terms will turn up a similar proof) and use that proof as the basis for your algorithm.

As Turing machines can simulate an NDFA, I assume an algorithm to produce an NDFA is good enough.

What s the difference between a recursive set and recursive function?

The meaning of these terms varies depending upon your context. If we were discussing them purely from the standpoint of writing programs then recursive sets don't make much sense; however, it might just be that I have encountered it yet. That said, recursive functions are functions that call themselves in their execution. The calculation of a nth Fibonacci number is the classic example that is commonly presented:

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

That said, the other context for these terms in the context of computer science and specifically the theory of computation is when discussing of formal languages. In this context, a recursive set is defined to be a set for which there is a solvable membership problem. For example, we know that the set of all natural numbers ℕ is a recursive set because we can define a recursive function as follows:

Let f be defined as a function where f(x) = 1 if x ∈ ℕ and f(x) = 0 if x ∉ ℕ

The concept of a recursive set is important for the concept of computability because it leads to the recursively enumerable set which is a language that can be recognized by a Turing machine (i.e. Turing-recognizable). These are languages for which a Turing machine may or may not be able to determine if a given string is a member of a language, or in other words, the machine may either accept, reject, or loop. This is in contrast to a Turing-decidable language for which a the machine will enter into either the accept or reject state for a given input string.

This where the concept of a recursive function comes in play, as a recursive function (or total recursive function) can be computed by a Turing machine and halts for every input. Where as a partial recursive function can only be computed for a Turing machine with no guarantee in regard to halting behavior. Or in essence the recursive function is the counterpart to the recursive set.

So to bring things back around to your original question, in the context of the theory of computation, a recursive set is what can be generated (i.e. enumerated) or have membership tested by a recursive function on a Turing machine.

Further Reading:

I have been writing PHP, Ruby, ColdFusion, and javascript (not a language, I know), for several years.

But I am really wanting to get more into the world of Computer Science and writing in lower-level languages.

What are some good resources for starting out? It seems like every book I have gotten has been extremely elementary, and that isn't at all helpful. I need something that skips the basics.

For computer science, I would recommend starting with discrete mathematics. A good book is the Rosen book, which my university uses. From there, you can move on to Concrete Mathematics, Introduction to Algorithms, and Introduction to the Theory of Computation. I can't speak much about Introduction to Algorithms - it's still on my wish list. But the other two are very good. That should cover the basics of computer science.

From there, you can go down any route. Some major fields in computer science are theoretical computer science (logic, automata theory), computational theory (computability theory and complexity theory), algorithms and data structures, computer architectures (parallel processing), operating systems, computer networks, graphics, vision, databases, AI...You would have to decide what interests you the most and investigate that particular topic area in more depth.