Pages: 22

In this chapter, you will learn about the basic mathematical objects that you will use throughout this book. You can think of this as analogous to learning about primitive data types (e.g., int or float) in a programming language. It is critical to understand these very well to be able to understand more complex ideas.

Pages: 11

We are now ready to study a simple model of computation. As computer scientists, we have to understand the computing models that we working with to determine what is easily computable and (later in this book) what is not computable at all. The first model of computation that we will study is called a deterministic finite automaton or DFA (plural: deterministic finite automata).

Pages: 14

It is not an exaggeration to say that mathematical logic underlies all of computer science. Computer circuits are made out of logical operators. The mathematical arguments we make about algorithms follow the rules of logic. Moreover, understanding logic will make you better at writing conditional (if) statements and (while) loops when you code.

Pages: 12

Nondeterministic Finite Automata (NFAs) allow us to create simpler, often smaller, automata for the same language. They are a generalization of DFAs that add in a property called nondeterminism. While nondeterminism is not something that any real computer can exhibit, it is an important concept for much of theoretical computer science. In particular, in later courses you will learn about hard NP-complete problems for which nondeterminism is an integral concept to understand.

Pages: 7

Regular expressions are a shorthand way to express regular languages. By using combinations of just three operations, we can express any regular language. In addition to their connection with regular languages, regular expressions are used extensively in string matching in text search and modern text editors, as well as for search utilities for the Unix command line.

Pages: 10

In this section we will see that the languages accepted by DFAs and NFAs are exactly the same as the languages of regular expressions. This means that we can use these two ideas interchangeably. Moreover, we will prove the equivalence constructively, which means that we will have a way to design a regular expression from any DFA and vice versa.

Pages: 10

Proofs are the means by which we demonstrate that an algorithm does what we intend for it to do. It is usually impossible to test all possible inputs to an algorithm so we have to make a logical argument about its correctness. Making rigorous arguments then is a critical skill for a computer scientist.

Pages: 20

Proof by induction is a key proof technique that is used extensively in computer science. It is used for proving correctness of algorithms with loops and recursion. It is also used for showing bounds on the run-time of many recursive algorithms. We'll also see how some of the results for sets and regular languages from earlier chapters can be formally proved.

Pages: 10

Now that you know how to create DFAs, you should next verify that the DFA you created does accept the language you think it does. This is analogous to showing that the algorithm you designed gives the correct answer on all possible inputs, something that every computer scientist should be doing.

Pages: 5

Proof by contradiction is a powerful technique that is often the best way to prove many results in computer science. It can be an easier way to prove some results than, say, direct proof because it allows the prover to assume more facts to be used in the proof.

Pages: 8

Now that you have learned about proof by contradiction, you will see how to apply it to show that certain languages are not regular—no matter how hard you try, you cannot create a DFA for them. This is our first taste of what is not computable with (a specific model of) computers. It also means that there are fairly simple problems for which we cannot design a DFA and thus DFAs are not the model of computation that we want to use to represent all computers.

Pages: 9

Now that we have established that DFAs are not powerful enough to capture all computation, we will look at a different way to model languages called Context-Free Grammars (CFGs). These grammars lay the foundation for all natural languages, such as English, Hindi, Spanish, and Vietnamese and programming languages, such as C++, Java, and Python.

Pages: 12

The Turing machine is the standard model for all computation. It is capable of accepting all regular languages, context-free languages, and indeed any language computation that is believed to be possible by a computer. All programming languages are called Turing-complete, which is an informal way of saying that they can do all that a Turing machine can do. Thus understanding how Turing machines work is important for any computer scientist.

Pages: 14

In this chapter we will study what Turing machines are capable of from a higher level and see why we believe this model of computation to be the one that captures everything we believe a computer capable of doing. We will then show that there is a problem that is uncomputable. Since we established Turing machines as our model of computation, we will see that no mechanical computer that currently exists or ever will exist can solve this problem. We will then show that a number of other problems are also uncomputable by bootstrapping from this one problem using a technique called a reduction, another important concept in computer science.