For the next several lectures, we're going to talk about theoretical computer science. In many scientific disciplines, people working in the discipline maybe can dismiss theory as something maybe not relevant to what they do daily. For computer science that's not really true. Theory is an integral part of our discipline and everyone should have a basic understanding of the type that we're going to talk about in the next couple of lectures. We'll begin with a brief overview of the basic issues. We're going to be talking about very fundamental questions relating to computation, like what can a computer do or if we have limited resources what can we do with a computer. There's a very general approach that mathematicians and computer scientists have used over the last five or six decades actually. First of all, we don't want to talk about specific machines or problems. We want to consider what's called abstract machines that have very minimal capabilities and we'll see some examples of that in this lecture. So, this is an example of a machine that we'll see at the end. And we'll consider very general classes of problems. So, the idea is to come up with the simplest machine that shares the characteristics of the actual machines that we use and the classes of problems that embody the classes of problems that we care about and try to say general statements. And the surprising outcome of this approach is, that we're going to have sweeping and very relevant statements about all computers. It's quite actually an amazing outcome that we'll get to in the next couple of lectures. And it doesn't matter whether it's a supercomputer, or a new laptop, or your phone, or an old PC, or an old mainframe, or even one of the first computers. All these computers share the same basic properties that we'll be able to articulate really quite precisely. So, in general there's a question of why study theory, even Yogi Berra had a comment on it. "In theory there's no difference between theory and practice. In practice there is." And we'll see that right away in this lecture. Certainly for theoretical computer science, we get a very deep understanding of computation that actually is the foundation of all the modern computers that we use. It really helps us understand the natural world and there's philosophical implications as well. In practice, there's all kinds of practical tools that have evolved out of the theoretical studies. So when you do web search, you need the theory of pattern matching which is very related to these basic computational questions circuits that we use to build computers or compilers that we use to translate from one programming language to another. Cryptography is based on theory, data compression, and many, many other fields have evolved from the basic understanding that we get from theoretical studies. So in this lecture, we're going to talk at both levels. We'll talk a little bit about theoretical questions, a little bit about practical questions and end up with some basic questions about computation. So, one thing we're going to talk about I already mentioned is the idea of abstract machines. So what an abstract machine is, is really a mathematical model of computation. Actually for the lecture, we have kind of a graphical model that mimics what you might imagine a real machine. So, there's different types of machines, they have different capability. Each machine is defined by very specific rules for taking input and producing output. This lecture we're going to talk about the simplest kind of abstract machine called a Deterministic Finite Automata and that's pictured at the right and we'll look at details in a minute. There's another idea called a formal language. A formal language is just a set of strings. Over on the right we have an example of a set of strings. So, that's the set of English language palindromes saying, does the thing read the same forward and backwards? So, that's a specific rule that characterizes this set of strings; reads the same forward and backwards. And you could have many other and matching many other types of rules if you can articulate the rules then you're defining a set of strings as a formal language. So, we're going to talk about a particular set of rules called regular expressions today and those turn out to be very useful in many applications. In this lecture, we're going to address some basic questions related to these obstructions. For example, we might want to know, is a given string in the language defined by a given regular expression or not? That already is an interesting question to approach. And we might say, well, if we had a computer could we answer this question? In particular, could a simple computer like a DFA answer this question? Already with these very simple models we come to interesting questions with useful practical applications. That's what most of this lecture is about.
