Hello everyone! This article is the first chapter on the series “Exploring Automata Theory” that I am publishing on. This article gives you an gentle introduction on what automaton theory is all about.
We will be seeing how to learn this mathematical side of CS using coding and good visualization techniques. This article is written in the view that even a person with no CS background can understand. Let’s get started.
So, what is Automata Theory?
Exact definition : Automata theory is the study of abstract computing devices, or “machines”.
Automata Theory is the study of how machines work, simply stated.
You might see the word “abstract machines” when you search for the proper definition of automata theory. Abstract machines is just a word to signify that these machines are basically developed or imagined for theoretical interest. Not all of them are implemented into programs or code. You study various machines in a hypothetical way and try to understand them.
So, why learn this particular theory ? What is so fascinating about it ?
Automata Theory is one of the vital concepts that is being used in our day-to-day life. You wouldn’t immediately recognize it but it has vital advantages.
Being a student myself, all of us think computers can do anything. We believe they are super humans actually. Let me tell you a secret that nobody has ever told you till now. Computers are not that. They are just machines that does work as per a human instructions. It is dumb and can’t think on its own. Unless you know how well to use it, it is of no use. Not all problems can be solved by it. Only a fraction of the total problems that exists can be solved and that too within a reasonable amount of time.
What the hell are you saying dude ?
Yes, whatever I just now said was the truth. But how did someone even find this out ? How could you prove this fact ? The answers to these questions are provided by this subject.
All the problems we have can be classified into two types :
Problems that can be solved efficiently by computer and,
Problems that can in principle be solved, but in practice take so much time that computers are useless for all but very small instances of the problem.
The latter class of problems is called “intractable,” or “NP-hard.” It is highly unlikely that even the exponential improvement in computing speed that computer hardware has been following (Moore’s Law”) will have significant impact on our ability to solve large instances of intractable problems.
Automata theory is of major help in order to classify the existing set of problems into the types I mentioned above. This tool will help you to beforehand know whether a problem can be solved or not. It saves you time to a great extent when you are developing some good software actually.
Most of us would say, “Hey ! Why don’t you give me a keyboard and computer, and I will just code “. Well, you can be that type of person. But understanding this theory not only enables you to understand how machines do work but also allows you to provide concrete proofs to validate the correctness of your program. It makes it easier to correct your mistakes and helps you to provide good generic solutions for the problem.
You might not able to understand all these concepts right now. Don’t worry about it. This is just the beginning. Just remember whatever you read now at the back of your mind and dive into this subject to find your answers.
References for interested readers :
- “Introduction To Automata Theory, Languages, and Computation”, 3 rd Edition by JOHN E. HOPCROFT, RAJEEV MOTWANI and JEFFREY D. ULLMAN — Chapter 1.
2. “Theory of Computation and Automata Theory”, YouTube Videos by NESO ACADEMY.
3. Automata Theory Standford Course taught by Jeffrey D. Ullman.
