Theory of Computation emphasis on formal languages, models of computation and computability, computational complexity and NP-completeness. It is basically a theoretical topic and this theory is used in many important computer applications you use every day.
Automata theory is the study of abstract computing devices. In 1930’s Alen Turing introduced an abstract machine that has all the capabilities of today’s computers, at least as far as what they could compute. These automata where originally proposed to model brain function, but turned out to be extremely useful for a variety of other purposes.
In 1950’s the linguist N. Chomsky began the study of formal grammars. These grammars have close relationships to abstract automata and serve today on the basis of some important software components, including parts of compilers.
What you are going to learn in this tutorial series
In these tutorials you are going to study all the topics mentioned above and you will learn about their practical application. Apart from that you are going to study about computational complexity and NP-completeness. These tutorials will include some practice questions related to theory and some programs. The answers are provided for every question.
Why you should study Automata
There are a number of reasons for you to study theory of computation if you are in the field of computer science. Some of those reasons are :
- It plays an important role when making software for designing and checking the behavior of digital circuits.
- It is used in the design of lexical analyzer phase and parser (syntax analyzer). The techniques used in there design can also be used for designing other software component.
- It is also used in developing the Scanning Software for large body of text to find occurrence of words, phrases or other patterns.
- Regular Expressions are used in pattern recognition.
- Automata theory is very useful for natural language processing.
Books to refer
If you want an in depth knowledge of the subject and more questions for practice you may refer to the books Introduction to Languages and Theory of Computation by John C. Martin or Theory of Computation by Peter Linz.
Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.
