hello everyone welcome to the first lecture in the course theory of computation in this lecture I will be giving you an introduction to the course theory of computation where we shall see what this course is all about what can we study from this course and what this course has to offer all right so let's get started so what is theory of computation this theory of comput ation is one of the most fundamental courses of computer science this course is one of the most fundamental as well as abstract courses of computer science which every computer scientist and Engineers must know this course is not going to help you write programs or build a computer as such but it will help you understand how people have thought about computer science as a science in the past 50 years okay so what does this mean and what is it really about so this subject is mainly about what kind of things can you really compute mechanically how fast can you do it and how much space does it take to do so okay so we know that in computer science there are certain kind of problems that a computer or a machine can solve and also there are certain kind of problems or things that a machine cannot do or certain kind of things that a computer cannot solve so we shall be seeing all these kind of things in this subject okay so we talked about how fast and how much space does it take to do so so let us just leave these two points for a while and let us just focus on about what kind of things can you really compute mechanically so to make this point clear let us take a simple example so let's say I want to design a machine that accepts all binary strings that end in zero I want to design a machine that accepts all binary strings that end in zero so my machine that I designed should accept all binary strings that end in zero and should reject all other strings that does not end in zero okay so let me take an example string here let's say 11 1 0 1 0 1 1 0 so this is my example string that I have here okay now now what I want to do is I should check whether this string is accepted by my machine so as a human being how would I perform this task as a human being I would just look at the last digit and if I see that it is zero I say yes I accept it or if I find that it is equal to one I say no I reject it so how would a machine do this a machine would scan the last digit and if it finds that it is equal to Zer it says yes it is accepted or if it finds that it is equal to one it says no and it rejects it why because our machine is supposed to accept all binary strings that end in zero okay so that was fairly a very simple example now let us take another example in this example I want to design a machine that accepts all valid Java code it accepts all valid Java codes okay so what should my machine do my machine should check the binary equivalent of my codes when I write a code in Java it should check the binary equivalent of this codes and from this binary equivalent it should tell whether this came from a valid piece of java code or it is invalid okay so my question is is it possible to design this kind of a system the answer to this is absolutely yes we can and the best example I can give for this is compilers when we write a piece of code into our compilers let's say that I'm writing a piece of java code so I write a piece of java code into my compiler and when I compile that program if if I have written that program correctly without any mistakes the compiler compiles that program and runs it because it is valid on the other hand if you have made some mistakes in that code or if you have written something wrongly then the compiler tells you that there is an error and it does not run the program because it is invalid all right so we can we see that it is very much possible to design this kind of a system and from this example I I think we got a slight hint that the whole of compiler design it came from this subject theory of computation okay so I hope that was clear now let's take another example now in this example I want to design another system that that accepts all valid Java codes and never goes into Infinite loop I assume you know what is the meaning of infinite Loop okay so I want a machine that accepts all valid Java codes and do not go into Infinite Loop so is it possible to design this kind of a system so from this uh previous example we have found that it is possible to design a system that accepts all valid Java codes this part is possible it's fine but we have one more condition here and never goes into Infinite Loop can I design a system that never allows my code to go into an infinite Loop the answer to this is no I can never design a system that performs this task okay so even if you design it you would either get the wrong output or it could run forever and give you no output at all so this kind of a machine that performs this kind of a task cannot be designed okay so this third example has given us an idea about what kind of things can we not compute mechanically okay I hope that was clear so what is this subject all about this Sub in this subject what we usually do is that we have a we have a system or a machine we design a machine and suppose this is a machine and then we send an input to this machine and then the machine thinks about this input based on some formula or based on some rules and it either says yes and it accepts the input or it rejects the input so this is what we are going to basically do in this subject we are going to design systems or machines which can take certain kind of inputs and this machine will be based on some rules and it should either accept the input or reject the input so this will be the thing that we'll be doing don't worry even if it is a little unclear right now when we take uh other examples and when we start from the very Basics from the following lectures it will all become very clear okay now now let us see what are the layers or the levels in this subject that we have to go through for that I will show you a diagram over here so here I have a small diagram showing the layers or levels in this subject so in the first layer we have FSM so what is FSM FSM stands for finite State machine FSM stands for finite state machine this FSM that is finite State machine it is one of the simplest model of computation it is the simplest model of computation and it has a very very limited amount of memory and it can perform very lowlevel computations and calculations okay this is the basic building block of this subject this is the first thing that we will be learning so keep in mind FSM it will be starting starting with it in the following lectures from the very Basics so don't worry even if you don't understand these terms now we will make make it clear as we go further and then the next layer we have is CFL CFL CFL stands for context free language context free language CFL stands for context free language and CFL is a little more powerful than FSM and it can perform some more higher level of computations as compared to finite State machines okay uh and one thing to remember here this language over here this language here does not mean a programming language okay when we in computer science when we come across the term language we often think oh this means a programming language but no in this subject here in this context free language this language actually mean means a set of strings a set of strings is what is known as language it'll become clear when we uh explain it further in the following lectures so don't worry about it and in the next layer we have something known as touring machine touring machine is a uh machine that can perform high level computations and calculations it was designed by alen touring in 1940 and it is much much more powerful as compared to context free language and final State machines okay and in the next layer we have this undecidable this is labeled as undecidable and why is that it is because the problems that cannot be solved mechanically those kind of problems it falls under this undecidable layer like for example above uh some time back we saw an example about a problem that could not be solved mechanically so those kind of problems that fall they fall under this undecidable layer okay so these are the layers that we have to go through and we will be starting with finite seit machines FSM in the next uh following lectures so we'll be start with the very Basics so don't worry even if you don't understand this terms that we used here it will become very clear as we start from the very Basics from the next lecture onwards so thank you for [Music] watching [Music]