Theory of Computation – An Overview

This sections gives a brief introduction of the Automata theory and Theory of Computation. In this secion we are also going to discuss the use of learning the theory of computation and where these concepts can be applied.

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 :

advertisement
advertisement
  • 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.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.